[백준] 11051. 이항계수2

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

 

이항계수 성질중 파스칼법칙을 써서 구하는데 시간초과가 나서 메모이 제이션으로 최적화 시켰다.

위키피디아에 이항계수검색하고 메모이제이션 검색하면 나올 것이다.

#include <cstdio>
const int MODULO = 10007;
int d[1003][1003];

// pascal's rule
int binomial_coefficient(int n, int k) {
    if (n == k || k == 0) {
        return 1;
    }else if (d[n][k] == 0) {
        d[n][k] = (binomial_coefficient(n-1,k-1) + binomial_coefficient(n-1, k))%MODULO;
    }  
    return d[n][k];
}
int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    printf("%d\n", binomial_coefficient(n,k));
}