[DP] [백준 / 11051] 실버 2 - 이항 계수 2 (java/자바)

문제

접근

이항 계수를 팩토리얼로 구하면 시간초과 문제가 있다.
두 이항계수의 합으로 현재 이항계수를 구한다.

성공 코드

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

public class Main {
    private static final int MOD = 10007;

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

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

        for (int i = 0; i <= N; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
        }

        for (int n = 1; n <= N; n++) {
            for (int k = 1; k <= K; k++) {
                dp[n][k] = (dp[n - 1][k - 1] + dp[n - 1][k]) % MOD;
            }
        }

        System.out.println(dp[N][K]);
    }
}