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

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

( 문제 바로가기 )

[ 문제를 다시 푸는 과정에서 이 문제에 대한 풀이를 다시 포스팅 하였습니다.

  아래의 글을 읽으셔도 문제를 푸는데는 무관하지만, 보다 구체적인 설명을 원하시는 분들께서는

  아래의 링크를 이용해 주시면 감사하겠습니다.

  [ 백준 이항계수2(11051) 새로운 포스팅 ]

]

[ 문제풀이 ]

1) 먼저 본인은 이 문제를 해결하기 위해 DP[][] 2차원 배열을 사용하였다.

   DP[a][b]의 의미는 (a b) 를 의미한다.

   [ 를 쓰기 편하게 (N K) 라고 쓰겠다. ]

   먼저 알아둬야할 초기값들이 있다.

   N값과 상관없이 K = 1 이라면 (N K)의 값은 무엇일까?? 답은 N이다

   그렇다면 N = K 라면 (N K)의 값은 무엇일까?? 답은 1이다.

   이 조건들을 초기식으로 사용하였다.

  

   그렇다면 문제에서 핵심적으로 사용되는 이항계수를 구하는 공식을 알아보자.

   공식은 DP[a][b] = DP[a-1][b-1] + DP[a-1][b]가 된다.

   이 공식을 알고 있었다면 쉽게 풀 수 있는 문제이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1001
#define Moduler 10007
using namespace std;
 
int N, K;
int DP[MAX][MAX];
 
void Input()
{
    cin >> N >> K;
    if (N < 1 || K < 0 || K > N) exit(0);
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        DP[i][1] = i;
        DP[i][i] = DP[i][0] = 1;
    }
 
    for (int i = 3; i <= N; i++)
    {
        for (int j = 2; j < i; j++)
        {
            DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][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;
}