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

백준의 이항계수2(11051) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

※ 문제 풀이를 시작하기 전에...

문제에서 나오는 라는 기호를 특수문자로 적을 수가 없어서, 이 글에서는 간편하게 [ N K ] 로 표시하도록 하겠습니다.

[ N K ]는 N ! / (K !(N - K)! 로 구할 수가 있다.

그런데 이렇게 일일이 구하면 너무 많은 시간이 걸릴수가 있다.

그래서 파스칼의 법칙을 이용해서 간단한 점화식을 도출 후 문제를 풀어볼 것이다.

파스칼의 법칙은 [ N K ] + [ N K+1 ] = [ N+1 K+1 ] 이라는 것이다.

그럼, [ N K ] = [ N-1 K-1] [ N-1 K ] 로 구할 수가 있다. 이를 점화식으로 문제를 풀어볼 것이다.

그런데, 고려해줘야 할 것이 몇 가지 있다.

# Case1 : N = 0

N = 0 인 경우에는 N - 1 값에 음수가 발생하기 때문에 계산이 제대로 될 수가 없다.

또한, 계산을 해보지 않아도, N = 0이라면, [ N K ] 의 값은 0이 된다.

# Case2 : K = 0

K = 0인 경우에도 K - 1 값에 음수가 발생하게 된다.

그리고 [ N K ]에서 K가 0인 경우에 결과값은 1이 된다.

위의 2가지 경우만 따로 계산을 진행해주면 된다.

이를 구현하기 위해서, DP[][]라는 2차원 배열을 사용해 주었는데, DP[A][B] = C의 의미는, [ A B ]의 결과값은 C 입니다 를 의미한다. 따라서 우리가 위에서 알아본 파스칼의 법칙에 의해서 점화식을 적어보면

DP[N][K] = DP[N - 1][K - 1] + DP[N - 1][K] 가 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
#define MODULER 10007
using namespace std;
 
int N, K;
int DP[MAX][MAX];
 
void Input()
{
    cin >> N >> K;
}
 
void Solution()
{
    if (N == 0)
    {
        cout << 0 << endl;
        return;
    }
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= K; j++)
        {
            if (j == 0) DP[i][j] = 1;
            else if (i == j) DP[i][j] = 1;
            else DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j];
 
            DP[i][j] = DP[i][j] % MODULER;
        }
    }
    cout << DP[N][K] % MODULER << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}