[BOJ] 11051 이항 계수 2

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > memo;

int main(void)
{
    int n, k;

    scanf("%d %d", &n, &k);
    memo.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i)
                memo[i].push_back(1);
            else
                memo[i].push_back((memo[i - 1][j - 1] + memo[i - 1][j]) % 10007);
        }
    }
    printf("%d", memo[n][k]);

    return 0;
}

첫 번째 풀이는 1부터 n까지 각 팩토리얼에 mod 10007을 취한 값을 저장하고 N!/K!/(N-K)!을 구하는 방법이었다.
이 문제 분류가 DP인 걸 생각하면 이렇게 푸는게 아닐 것 같았지만 제출은 해봤다. 역시 틀렸음. 분자가 분모보다 작아져 N이 8쯤 되면 답으로 0이 나왔다.
구글에 이항 계수를 검색하고 위키백과를 누르니 파스칼의 삼각형이란게 있길래 그대로 구현했다.
아니... 사실 본 적 있다. 파스칼의 삼각형. 하지만 안쓰면 잊어버리는 법...
nCk = n-1Ck-1 + n-1Ck
이 식도 언젠가 쓴 적 있겠지... 지금 썼으니 기억에 좀 오래 남아주길 바란다.
DP보다는 수학문제를 푸는 기분이었다. DP를 몰라도 이항계수를 안다면 풀 수 있을 것이다.