[BOJ알고리즘, C++]#11051_이항 계수 2, 파스칼의 삼각형

 

[BOJ 알고리즘, C++] #11051_이항 계수 2, 파스칼의 삼각형

 

BOJ 알고리즘 문제 풀이, 11051_이항 계수 2

이항 정리와 동적 계획법을 통해  이항 계수를 구합니다.

 

---

 

문제

 

풀이

1. 이항 정리 : N! / K!(N - K)!
2. 첫 번째 조건, C(N - 1, K - 1) = C(N - 1, K) 
3. 두 번째 조건, N = 0 일 때, C(N, K) = 0입니다.
4. 세 번째 조건, K = 0 일 때, C(N, K) = 1입니다.
5. DP [ N ] [ K ], 이차원 배열을 통해 동적 계획법을 활용하면 문제를 푸는 것은 그다지 어렵지 않습니다.

 

코드

/*
    문제:
        C(N,K) % 10007 결과 출력
    설명:
        1. N! / K!(N-K)!
        2. 파스칼의 삼각형 or 파스칼 공식 이용
        3. C(N-1, K-1) = C(N-1, K)
        4. 추가적으로, if N=0, C(N,K) = 0 이며, if K=0, C(N,K) = 1
        5. 동적 계획법을 통해 DP[N][K] 의 값을 구합니다.
*/

#include <iostream>
typedef long long ll;
using namespace std;

int N, K;
ll DP[1001][1001] = {0,};

int main()
{
    cin >> N >> K;

    if(N == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    for(int i=1; i<=N; i++)
    {
        for(int j=0; j<=K; j++)
        {
		// C( N , K ) 중 K = 0 일 때, 결과 값은 무조건 1입니다.
		if(j == 0) DP[i][j] = 1;
		// C( N , K ) 중 N = K 일 때, 결과 값은 무조건 1입ㄴ다.
		else if(i == j) DP[i][j] = 1;
		// C( N , K ) = C ( N - 1, K - 1) + C ( N - 1, K ) 입니다.
		// * 파스칼의 삼각형 활용
		else DP[i][j] = DP[i-1][j-1] + DP[i-1][j];

		DP[i][j] %= 10007;
        }
    }

    cout << DP[N][K] % 10007 << endl;
}