[백준] 11051번 : 이항 계수 2

문제

 

---

풀이

 

myunji.tistory.com/228

[백준] 11050번 : 이항 계수 1

이걸 동적 계획법으로 푸는 문제이다.

아마 학교에서 이항 계수에 대해 배웠을 때 파스칼의 삼각형도 들어봤을 것이다.

 

 

nCk = n-1Ck-1 + n-1Ck

라는 공식을 기억하고 있다면 어렵지 않다.

---

소스코드

 

#include <iostream>
using namespace std;

int dp[1001][1001] = { 0, };

int binomial(int N, int K) {
    if (N / 2 < K)
        K = N - K;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= K && j <= i; j++) {
            if (j == 0 || j == i) //4C0, 4C4 같은 끄뜨머리
                dp[i][j] = 1;
            else {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007; //오버플로우 방지
            }
        }
    }
    return dp[N][K];
}

int main() {
    int N, K;

    cin >> N >> K;
    cout << binomial(N, K);
}