[백준] 11051번: 이항 계수 2 풀이 및 해설(C++)

문제 이미지

풀이

이항계수 공식을 이용해야 한다.

N과 K를 공식으로 쓰면

nCk = nC(k-1)+(n-1) C(k-1)가 나온다.

즉, 초깃값부터 다이나믹 프로그래밍으로 풀어야 한다.

단 여기서, 10007로 나눈 나머지를 원했으므로 숫자 범위 추가를 조심해야 한다. 

 

해답 코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main()
{
    fastio;
    int dp[1001][1001]={0};
    unsigned int n,r;
    cin>>n>>r;
    for(int i=1;i<n+1;i++){
        dp[i][1]=i;
        dp[i][i]=1;
        dp[i][0]=1;
    }
    for(int i=2;i<n+1;i++){
    for(int j=1;j<r+1;j++){
    dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%10007;
    }
    }
    cout<<dp[n][r];
    
    return 0;
}

해맸던 부분

예전에는 여기에 dp가 아닌 재귀함수를 써서 타임오버가 나왔다. 

재귀함수 쓰는 것보다는 dp가 더 빠른 것 같다.