백준 11051번: 이항 계수 2

[문제 링크]

11051번: 이항 계수 2

---

이항 계수를 구하는 점화식을 이용하여 쉽게 풀 수 있는 문제였다.

---

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 10007;
int memo[1001][1001];

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

	int& ret = memo[N][K];
	if (ret != -1) return ret;

	return ret = ((Topdown(N - 1, K - 1) % MOD) + (Topdown(N - 1, K) % MOD)) % MOD;
}

int Bottomup(int N, int K)
{
	memo[1][0] = memo[1][1] = 1;

	for (int i = 2; i <= N; i++)
		for (int j = 0; j <= i; j++)
			memo[i][j] = ((memo[i - 1][j] % MOD) + (memo[i - 1][j - 1] % MOD)) % MOD;

	return memo[N][K];
}

int main(void)
{
	int N, K;
	cin >> N >> K;

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, K) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 86 day