BOJ) 다리 놓기

다리 놓기

1010번: 다리 놓기

풀이

 

강의 왼쪽과 오른쪽에 다리를 건설하는데, 교차해서 지으면 안되는 조건의 문제다.

왼쪽보다 오른쪽에 다리를 지을 수 있는 포인트가 더 많다.

여기서 Combination 문제라고 생각했다.

하지만, 30이나 되는 수에서 직접 Combiantion을 구할 수 없었기 때문에 수학 공식을 찾아봤다.

 

nCr = n-1Cr-1 + n-1Cr 이라는 공식이 있다는 것을 알았다.

앞으로는 콤비네이션을 이용해 푸는 문제를 만났을 때, 더욱 효율적으로 풀기 위해 공식을 남기기 위해 기록한다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private final static int MAX = 29;
    private final static String newLine = "\n";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine());
        int[][] dp = getAllCases();
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            sb.append(dp[right][left]).append(newLine);
        }
        System.out.println(sb.toString());
        br.close();
    }

    private static int[][] getAllCases() {
        int[][] result = new int[MAX+1][MAX+1];
        result[1][0] = 1;
        result[1][1] =1;

        for(int n=2; n<=MAX; n++) { // nCr = n-1Cr-1 + n-1Cr
            result[n][0] =1;
            for(int r=1; r<=n; r++) {
                result[n][r] = result[n-1][r-1] + result[n-1][r];
            }
        }
        return result;
    }
}