11051 : 이항계수2 (Binomial Coefficient) (Dynamic Programming) [C++]

저번 이항 계수의 문제와 비슷하지만

입력 값의 범위가 1000까지 늘어서 DP를 이용하기에 딱 좋은 문제이다.

왜 DP를 이용하는가?

이항계수의 원리를 보면 파스칼의 삼각형 형태!

1

1(1C0) 1(1C1)

1(2C0) 2(2C1) 1(2C2)

1(3C0) 3(3C1) 3(3C2) 1(3C3)

1(4C0) 4(4C1) 6(4C2) 4(4C3) 1(4C4)

1(5C0) 5(5C1) 10(5C2) 10(5C3) 5(5C4) 1(5C5)

1(6C0) 6(6C1) 15(6C2) 20(6C3) 15(6C4) 6(6C5) 1(6C6)

<파스칼의 삼각형(이항원리)>

DP식을 써보면

///////////////////////////////////////////////////////////

if (k == 0 || k == n)

       DP[i][j] = 1;

else

       DP[i][j] = DP[i-1][j-1] + DP[i-1][j];
///////////////////////////////////////////////////////////

BinomialCoefficient::BinomialCoefficient(int N)
{
    for(int i = 0; i < N; i++)
    {
        vector<int> Temp;
        Temp.resize(i+2);
        DP.push_back(Temp);
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i + 2; j++)
        {
            if(j == 0 || j == i + 1)
                DP[i][j] = 1;
            else
                DP[i][j] = DP[i-1][j-1] % 10007 + DP[i-1][j] % 10007;
        }
    }
}

void BinomialCoefficient::Print(int N, int K)
{
    cout << DP[N-1][K] % 10007;
}

<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/11051

*문제 출처 : BAEKJOON ONLINE JUDGE