[BOJ 11051] 이항계수2

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

무작정 하면 자료형 범위를 벗어난다. 따라서 파스칼의 삼각형 공식을 사용하여 문제를 해결하게 된다.

nCr = n-1Cr + n-1Cr-1 을 사용하면 된다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
typedef long long ll;
 
using namespace std;
 
int n,k,dp[1111][1111];
 
int solve(int a,int b){
    if(dp[a][b] >0){
        return dp[a][b];
    }
    if(a == b || b == 0){
        return dp[a][b] = 1;
    }
    return dp[a][b] = (solve(a-1,b-1)+solve(a-1,b))%10007;
}
 
int main(){
    memset(dp,0,sizeof(dp));
    ios::sync_with_stdio(false);
    cin >> n>>k;
    cout << solve(n,k)%10007 <<endl;
    
    return 0;
}