[백준/C,C++] 11051번: 이항 계수 2

www.acmicpc.net/problem/11051

11051번: 이항 계수 2

DP를 이용해 이항 계수를 푸는 문제입니다. 이항 계수 $\binom{N}{K}$ 는 $\frac{n!}{k!(n-k)!}$ 로 나타낼 수 있습니다.

 

하지만 주어지는 수의 범위가 $1 \le N \le 1,000, 0 \le K \le N$ 으로,

팩토리얼을 그대로 구현해서 쓴다면 값이 매우 커지게 됩니다.

값이 매우 커지기 때문에 모듈러 연산을 한 값을 출력해야 하는데,

모듈러 연산은 분수에 적용하기 힘들어 해당 값을 구할 수 없게 됩니다.

 

 

이항 계수를 기하학적 형태로 표현한 파스칼의 삼각형이라는 것이 있습니다.

예제 입력인 5 2 는 10인데, 바로 위 왼쪽과 오른쪽의 수 4와 6을 합친 값과 같습니다.

 

즉 $\binom{5}{2} = \binom{4}{1} + \binom{4}{2}$ 라는 거죠.

 

파스칼의 삼각형(출처 : 위키백과)

 

그렇다면, DP[y][x] = DP[y-1][x-1] + DP[y-1][x] 라는 점화식이 도출되는데,

상향식 동적 계획법인 타뷸레이션을 이용해 간단히 해결할 수 있습니다.

 

#include<iostream>

using namespace std;

#define MAX 1001

int DP[MAX][MAX];

void binomial()
{
    DP[0][0] = 1;
    for (int i = 1; i < MAX; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) DP[i][j] = 1;
            else {
                DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j]) % 10007;
            }
        }
    }
}

int main(void)
{
    int n, k; cin >> n >> k;

    binomial();

    cout << DP[n][k];

    return 0;
}