[C++] 백준 - 11051 : 이항 계수 2

문제 링크

11051번: 이항 계수 2

 

풀이 ) DP

  이항 계수 공식을 이용한 풀이이다.

  _nC_k = 1 ( k = 0 or k = n ), _n-1C_k-1 + _n-1C_k ( 0 < k < n )

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1002][1002];

int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= i && j <= k; ++j){
            if(j == 0 || j == i)
                memo[i][j] = 1;
            else
                memo[i][j] = (memo[i-1][j-1]+memo[i-1][j]) % 10007;
        }
    printf("%d\n", memo[n][k]);
    return 0;
}

 

주의점 )

  - k = 0, k = n일 때 1로 처리

  - 모듈러 연산