[#11051] 이항 계수 2

#include <iostream>
#include <vector>
#define mod 10007
 
using namespace std;
 
vector<vector<int>> dp(1001, vector<int>(1001, -1));
 
int findAnswer(int n, int k) {
    if (n == k || k==0) {
        dp[n][k] = 1 ;
        return 1;
    }
 
    if (k == 1) {
        dp[n][k] = n % mod;
        return dp[n][k];
    }
 
    int& ret = dp[n][k];
 
    if (ret != -1)
        return ret;
 
    return ret = (findAnswer(n - 1, k) + findAnswer(n - 1, k - 1)) % mod;
}
 
int main() {
    int n, k;
    cin >> n >> k;
 
    cout << findAnswer(n, k);
 
    return 0;
}

 

(n k) = (n-1 k) + (n-1 k-1)

 

기저사례로는

1) n==k, dp[n][k]=1;

2) k==0, dp[n][k]=1;     //이걸 몰랐음

3) k==1, dp[n][k]=n;

 

그리고 mod연산은 분배 법칙 XXXXX