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

문제

백준 11051

11051번: 이항 계수 2

풀이

nCr = n * (n -1) * (n-2) * ... * (n-r+1) / r! 이지만

n과 r이 커지면 오버플로우가 발생합니다.

따라서 파스칼의 법칙을 사용하여 dp로 해결합니다.

위 그림을 보면 nCr에서 r이 0이거나, n = r일 때는 1, 나머지 경우에는 nCr = n-1Cr-1 + n-1Cr 입니다.

1C0과 1C1의 초기값을 설정해주고 dp를 이용해 nCk을 구합니다.

소스 코드

#include <iostream>
#define num 10007
using namespace std;
 
int dp[1001][1001];
int n, k;
int main() {
    cin >> n >> k;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (j == 0 || i == j) {
                dp[i][j] = 1;
            }
            else {
                // 파스칼의 삼각형
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                dp[i][j] %= num;
            }
        }
    }
    cout << dp[n][k];
    return 0;
}