[백준] 1010번 : 다리놓기

문제

www.acmicpc.net/problem/1010

1010번: 다리 놓기

문제해결방법

이 문제는 n과 m이 주어지면 m개 중에 n개를 고르는 조합 문제였다.

제한시간이 0.5초라 시간을 줄이기 위해서 미리 구할수 있는 모든 조합의 수를 계산해두기로 했다.

처음에는 1부터 모든 n까지의 곱 DP를 계산하고 m개에서 n개를 구할 때 DP를 사용해서 구할려고 했다. 

그런데 위와 같은 방법은 자료형의 범위를 초과해서 1C1~mC1 을 구하고 미리 계산해둔 것들을 이용해서 2C2~mC2 를 구하는 방식으로 변경해주었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main1010_다리놓기 {
    public static long[] go = new long[31];
    public static long[][] DP = new long[31][31];
    
    public static void main(String[] args) throws Exception{
        for(int i=1; i<DP.length; i++) DP[1][i] = i;
        for(int i=2; i<DP.length; i++) {
            for(int j=i; j<DP.length; j++) {
                if(i==j) DP[i][j] = 1;
                else DP[i][j] = (DP[i-1][j]*(j-i+1))/i;
            }
        }
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            bw.write(DP[N][M]+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.