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

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

문제

---

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N과 K\가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

 

출력

---

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

 

문제 풀이

---

다이나믹 프로그래밍 문제.

 

_NC_K = _N-1C_K-1 + _N-1C_K임을 이용해 2차원 dp 배열을 채워주면 된다. 따라서 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]가 성립한다.

_NC₀와 _NC_N은 각각 N개 중 아무것도 뽑지 않는 경우와 N개 중 N개를 모두 다 뽑는 경우이므로 둘 다 1이다. 따라서 dp[i][0]= dp[i][i] = 1이다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;
	int** arr = new int*[N + 1];
	for (int i = 0; i < N + 1; i++)
	{
		arr[i] = new int[N+1];
		for (int j = 0; j < N+1; j++)
		{
			arr[i][j] = 1;
		}
	}
	for (int i = 1; i <= N; i++)
	{
		arr[i][0] = 1;
		arr[i][i] = 1;
		for (int j = 1; j < i; j++)
		{
			arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
			arr[i][j] %= 10007;
		}
	}
	cout << arr[N][K] << "\n";
	return 0;
}