[백준 11051] 이항 계수 2, C++

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

11051번: 이항 계수 2

본 문제는 이항 계수의 성질을 이용하여 푸는 문제다. 이항 계수는 (n, k) = (n-1, k) + (n-1, k-1)의 식이 성립하고, (n, 0) = 1, (i, i) = 1 (단, 1 <= i <= n) 이 성립한다. 따라서 d[n][k] = d[n-1][k] + d[n-1][k-1]의 점화식을 정의할 수 있고 mod 연산의 결과를 출력해야 하기 때문에 d[n][k] = ( ( d[n-1][k]%mod ) + ( d[n-1][k-1]%mod ) ) 으로 정의하여 문제를 해결할 수 있다.

#include <cstdio>
 
using namespace std;
 
int d[1001][1001];
 
int const md = 10007;
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i <= n; i++) {
        d[i][0] = 1;
    }
    for (int i = 0; i <= k; i++) {
        d[i][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            d[i][j] = ((d[i-1][j]%md) + (d[i-1][j-1]%md))%md;
        }
    }
    printf("%d\n", d[n][k]);
}