백준 1010번 다리 놓기

조합으로 해결할 수 있는 문제다.

 

조합 공식

위와 같은 조합 공식에 따라 팩토리얼을 구현하여 문제를 풀이할 수도 있지만, 단순 계산으로 풀이한다면 계산량이 매우 클 것이다. 

 

조합의 성질 1.

조합의 성질 2

 

따라서 조합의 2가지 성질과 동적 프로그래밍을 활용하여 풀이하였다.

 

import java.util.Scanner;

public class Main {

    static int[][] dp = new int[30][30];

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int T = in.nextInt();

        for (int i = 0; i < T; i++) {
            int N = in.nextInt();
            int M = in.nextInt();

            sb.append(combination(M, N)).append('\n');
        }
        System.out.println(sb);
    }

    public static int combination(int n, int r) {

        // 이미 풀렸을 경우
        if (dp[n][r] > 0) {
            return dp[n][r];
        }

        // nC0 = nCn = 1
        if (r == 0 || n == r) {
            return dp[n][r] = 1;
        }

        // (n+1, r+1)C = (n, r)C + (n, r+1)C
        return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
    }
}