[백준 11051 : JAVA] 이항 계수2 / 조합 + DP

문제

---

 

 

 

풀이

---

이항 계수: n개의 서로 다른 물건 중에서 순서없이 k개를 뽑는 가짓수

이항 계수를 식으로 표현 ---> $n \choose k$ = $\frac{n!}{k!(n-k)!}$ = ${}_n \mathrm{ C }_k$

 

위의 이항 계수의 공식대로 팩토리얼로 풀게될 경우 N의 최대값이 1000이기 때문에 $1000!$를 계산해야되서 적절하지 못하다.

대신, 파스칼의 삼각형 원리를 이용해 DP로 풀 수 있다.

 

[그림 1] 파스칼의 삼각형

 

즉, ${}_n \mathrm{ C }_k$ = ${}_{n-1} \mathrm{ C }_{k-1}$ + ${}_{n-1} \mathrm{ C }_k$ 라는 식을 이용한다.

 

 

 

코드

---

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[][] dp = new int[N + 1][N + 1];

            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j <= i; j++) {
                    if (i == j || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
                    }
                }
            }

            System.out.println(dp[N][K]);
        } catch (Exception ex) {
            ex.getMessage();
        }
    }
}