JAVA 백준 11051번 이항 계수 2

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수(binom{N}{K})를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N))

출력

 (binom{N}{K})를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

5 2

예제 출력 1 

10

알고리즘 분류

조합론(combinatorics), 다이나믹 프로그래밍(dp), 수학(math)

소스코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        if (K > N / 2) {
            K = N - K;
        }

        int[][] binomail = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            int k = Math.min(i, K);
            for (int j = 0; j <= k; j++) {
                if (j == 0 || j == i) {
                    binomail[i][j] = 1;
                } else {
                    binomail[i][j] = (binomail[i - 1][j - 1] + binomail[i - 1][j]) % 10007;
                }
            }
        }
        System.out.println(binomail[N][K]);
    }
}