[백준] 11051번. 이항 계수2(JAVA)

문제

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

---

풀이(20분)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long[][] dp = new long[1001][1001];
        int MOD = 10007;

        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
            }
        }

        System.out.println(dp[n][k]);
    }
}

 

초반 수학적 개념만 사용하여 직접 팩토리얼을 계산하려고 하였으나 이는 문제 해결에 있어 너무 많은 계산을 요구했다.

 

따라서 파스칼 삼각형을 이용한 dp 배열을 사용하여 문제를 해결하였다.

 

코드 자체에 대한 이해보다는 파스칼 삼각형에 대한 이해만 있으면 충분히 문제를 이해할 수 있을 것이다.