11051번 이항 계수 2

 이항 계수에 대해 알고 있다면 간단한 DP문제.

 

 파스칼의 법칙을 이용했다.

 

 

 

 이 법칙에 의해 dp(n,k) + dp(n,k+1) = dp(n+1,k+1) 라는 점화식을 구할 수 있다.

-> n-1,k-1을 대입하면 dp(n-1,k-1) + dp(n-1,k) = dp(n,k) 라는 점화식 또한 구할 수 있다.

 

 구한 점화식을 이용해 풀면 된다. 

 

#include <iostream>
#define MAX 1001
#define mod 10007
 
using namespace std;
 
int dp[MAX][MAX];
int N,K;
 
void DP(){
 
    for(int i=0;i<=N;i++){
        dp[i][0]=1;
        
        for(int j=1;j<=i;j++){
            if(j<=K) dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
        }
    }
    
    cout << dp[N][K]%mod << endl;
}
 
int main(){
    cin >> N >> K;
    
    DP();
}