[백준 온라인 저지] 1010. 다리 놓기

1. 입력

- 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.

- 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

 

2. 출력

- 각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

- 조건: 서쪽의 사이트와 동쪽의 사이트를 연결할 다리 N개를 짓는데, 다리끼리 겹칠 수는 없다.

 

3. 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.valueOf(br.readLine());
        for(int i=0 ; i<n ; i++){
            StringTokenizer token = new StringTokenizer(br.readLine());
            int[] site = {Integer.valueOf(token.nextToken()),Integer.valueOf(token.nextToken())};
            bw.write(comb(site[0],site[1])+"\n");
        }
        bw.flush();
        bw.close();
    }
    static long comb(int r, int n) {
        long[][] B = new long[n+1][r+1];
        for(int i=0 ; i<=n ; i++) {
            for(int j=0 ; j<=Math.min(i, r) ; j++) {
                if(j==0 || j==i)
                    B[i][j] = 1;
                else
                    B[i][j] = B[i-1][j-1] + B[i-1][j];
            }
        }
        return B[n][r];
    }
}

- 조합 계산은 iterative가 recursive보다 빠르다.