(Java) 백준 11051번 - 이항 계수2

https://www.acmicpc.net/problem/11051

문제

> 자연수 N과 정수 K가 주어졌을 때, 이항 계수 (N, K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

접근

dp를 사용하여 파스칼의 삼각형으로 N,K를 구한다.
dp(i,1)은 항상 i가지를 가지고 dp(i,i)는 항상 1가지를 가진다. 작은 수 일때의 이항계수를 구해보면 dp(i,j)는 dp(i-1,j-1) + dp(i-1,j)를 만족한다는 규칙을 찾을 수 있다.

문제해결

> N과 K를 입력받고 이차원배열 dp를 선언한다.
> 파스칼 삼각형을 사용하기위해 N+1,N+1크기로 주고 이중반복을 돌린다.
> i,0과 i,i는 항상 1이므로 이를 처리해주고 나머지 경우를 처리한다.
> i,1부터 i,i-1까지는 파스칼의 삼각형을 이용해 구한다.
> i,j는 i-1,j-1과 i-1,j의 합이다. 문제에서 10007로 모듈러 연산 조건으로 줬으므로 해준다.
> 원하는결과인 dp(N,K)를 출력한다.

코드

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

public class Main {
    //11051번 이항 계수2
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, K;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int[][] dp = new int[N+1][N+1];
        for(int i = 0; i <= N; i++) {
            dp[i][0] = dp[i][i] = 1;
            for(int j = 1; j < i; j++) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007;
            }
        }
        System.out.print(dp[N][K]);
    }
}

후기

팩토리얼을 메소드로 구현해서 해봤지만 수가 너무커서 dp로 풀어야한다고 한다. 예전에 한번했었는데 꽤 헤맸다. 이번에 많은 오류, 시행착오로 좀 제대로 알게됐다.