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

11051번 : 이항 계수 2

---

문제)

자연수 N과 정수 K가 주어졌을 때 

를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 N과 K가 주어진다. (1 <= N <= 1.000. 0 <= K <= N)

 

 

 

출력 :

를 10,007로 나눈 나머지를 출력한다.

 

 

 

 

 

풀이)

 

나오는 규칙을 표로 그려보면

 

	1	2	3	4	5
1	1	X	X	X	X
2	2	1	X	X	X
3	3	3	1	X	X
4	4	6	4	1	X
5	5	10	10	5	1
6	6	15	20	15	6

의 규칙으로

점화식이  dp[i][j] = dp[i - 1][j -1] + dp[i - 1][j] 이 됨을 알 수 있다.

 

// 11051. 이항 계수 2
#include <iostream>
 
using namespace std;
 
int n, k;
int dp[1001][1001];
 
int main()
{
    cin >> n >> k;
 
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
 
    for (int i = 2; i < n + 1; i++)
    {
        for (int j = 0; j < i + 1; 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]) % 10007;
            }
        }
    }
 
    cout << dp[n][k];
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/11051 

11051번: 이항 계수 2