11051번 이항 계수 2

문제 링크

이항 계수 2

문제 풀이

이항 계수를 푸는 문제이고 아래의 공식이 점화식이 된다.

$\begin{pmatrix} N \\ K \end{pmatrix} = \begin{pmatrix} N-1 \\ K \end{pmatrix}+\begin{pmatrix} N-1 \\ K-1 \end{pmatrix}$

따라서 $n == k$ 또는 $k == 0$ 인 경우가 기저 사례가 된다.

구현

#include <iostream> 
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 10007;

int N, K, cache[1001][1001];

int solve(int n, int k) {
    if (n == k || k == 0) return 1;

    int& ret = cache[n][k];
    if (ret != -1) return ret;

    ret = (solve(n - 1, k) % MOD + solve(n - 1, k - 1) % MOD) % MOD;
    return ret % MOD;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    memset(cache, -1, sizeof(cache));

    cout << solve(N, K);
    return 0;
}