[백준] 11051 이항계수문제

해당문제는 이항계수문제로 n과 k가주어졌을경우

nCk % 10007을 한 결과를 구하는 문제입니다.

nCk = n-1Ck-1 + n-1Ck로 나타낼수있습니다.

이를 DP를 이용해서 풀면 cache[1001][1001] 배열에 nCk의 값을 저장해두고 해당 값이 필요할경우 배열에 있는 값을 이용하면 문제를 더욱빠르게 풀수있습니다.

#include <iostream>
#include <string.h>
using namespace std;
//이항계수
// 점화식  nCk = n-1Ck-1 + n-1Ck
typedef long long ll;
const ll divideNum = 10007;

ll cache[1001][1001];

ll Answer(int N, int K) {
	if (N == K || K == 0) return 1;

	ll& ret = cache[N][K];

	if (ret != -1) return ret;

	ret = (Answer(N - 1, K - 1) + Answer(N - 1, K)) % divideNum;

	return ret;
}

int main() {
	std::ios::sync_with_stdio(false);
	int N, K;
	memset(cache, -1, sizeof(cache));
	cin >> N >> K;

	cout << Answer(N, K) << endl;
	return 0;
}