BOJ 11051 이항 계수2 [Java]

문제

접근방법

• 처음에 재귀나 반복으로 풀었을 때는 시간초과가 난다.
• 그래서 아래 그림과 같이 이항계수를 다시 이해하고, 동적 계획법으로 풀이하였다.
  
  (출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vollollov&logNo=220947452823)

구현

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

class Main {

    public static void main(String[] args) throws Exception {
        // for coding
        // System.setIn(new FileInputStream("./input/input_11051.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ", false);

        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;
                }
            }
        }

        bw.write(dp[N][K] + "");

        bw.close();
    }
}

제출