백준 11051번 : 이항 계수

  중고등학교 때 엄청나게 많이 공부했던 잘 알고 있는 수학적 지식이였기에 쉽게 풀었다. 파스칼의 삼각형을 이용하면 된다.

 

이항 계수를 0C0부터 10C10까지 나열한 모습

 

  bico는 binomial coefficient(이항 계수)의 약자이다. 일반적인 파스칼의 삼각형 모양에 따르면 이항계수는 자신의 왼쪽 위와 오른쪽 위의 항을 합하면 된다. 또한 제일 가장자리의 값, 즉 j가 0이거나 j와 i가 같을 경우는 항상 1이다. 따라서 3가지 경우로 나눠서 bico[i][j]를 계산하면 된다.

 

• j == 0 일 경우 bico[i][j] = 1
• j == i 일 경우 bico[i][j] = 1
• 그 외의 경우 bico[i][j] = bico[i-1][j-1] + bico[i-1][j]

 

#include <iostream>

using namespace std;

int n, k;
int bico[1003][1003];

int main()
{
    cin >> n >> k;
    
    bico[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(j == 0) bico[i][j] = 1;
            else if(j == i) bico[i][j] = 1;
            else bico[i][j] = (bico[i-1][j-1] + bico[i-1][j]) % 10007;
        }
    }
    
    cout << bico[n][k];
    
    return 0;
}