[백준] 11051

이항 계수 2

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수

를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

출력

를 10,007로 나눈 나머지를 출력한다.

풀이

#include <iostream>

int dp[1001][1001];

int main(void) {
    int n, k;

    std::cin >> n >> k;

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

    std::cout << dp[n][k];
}

반성회

팩토리얼 곱셈으로 풀면 나머지 (%10007) 연산을 할 때마다 값이 잘못 나와서 틀리게 된다

dp 배열로 위와 같은 삼각형을 만들어서 dp[n][k] 의 값을 구해야 풀 수 있는 문제