[백준 11051] 이항 계수 2

자연수 N과 K가 주어졌을 때, 이항 계수 nCk 를 구하는 문제입니다.

 

해당 숫자를 10,007로 나누는 의미는 대부분 큰 숫자인 경우에 해당 숫자로 나누는 테크닉이 필요합니다.

이항 계수는 중요한 성질을 가지고 있습니다.

 

n과 k가 같을 때 혹은 k가 0일 때는 1입니다. 이를 통해 base condition 을 만족할 수 있고,

 

파스칼 법칙에 의하면 nCr = n-1Cr-1 + n-1Cr 을 만족하게 됩니다.

이러한 법칙을 하나씩 하다 보면 반복되는 구간이 생기게 됩니다. 반복되는 것을 계속해서 계산하는 것은 낭비입니다. 따라서 한 번 구한 답을 캐시에 저장하면, 이후에 꺼내다 쓰면 됩니다. 이것을 메모리제이션이라고 합니다.

 

위에서 base condition도 만족하지 않고, 메모도 하지 않았다면 적어도 한 번은 계산해야 되기 때문에

dp[n][k] = func(n - 1, k - 1) + func(n - 1, k) 를 통해 구하고 리턴합니다. 다만 주의할 점은 계산할 때마다 10,007 로 나누어 줘야 합니다.

 

따라서 dp[n][k] = (func(n - 1, k - 1) % 10,007 + func(n - 1, k) % 10,007) % 10,007

 

이렇게 푸는 방식을 dp(다이내믹 프로그래밍) 중에서도 Top-down 방식입니다.

#include <iostream>
using namespace std;

typedef long long ll;
int n, k;
ll dp[1001][1001];

const int MOD = 10007;

ll combination(int n, int k)
{
	if (dp[n][k] != 0) return dp[n][k];
	if (n == k || k == 0) return 1;

	dp[n][k] = (combination(n - 1, k - 1) % MOD + combination(n - 1, k) % MOD) % MOD;

	return dp[n][k];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	cout << combination(n, k) << endl;
	return 0;
}