백준 2225번: 합분해

[문제 링크]

2225번: 합분해

---

간단한 dp 문제였다.

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 방법은 다음과 같다.

i를 0부터 N까지 반복하고 0부터 (N-i)까지의 정수 (K-1)개를 더해서 그 합이 (N-i)가 되는 경우의 수를 누적 시켜주면 된다.

---

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

const int MOD = 1000000000;
int memo[201][201];

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

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

	ret = 0;

	for (int i = 0; i <= N; i++)
	{
		ret += Topdown(N - i, K - 1);
		ret %= MOD;
	}

	return ret;
}

int Bottomup(int N, int K)
{
	for (int i = 0; i <= N; i++)
		memo[i][1] = 1;

	for(int i=2; i<=K; i++)
		for(int j=0; j<=N; j++)
			for (int k = 0; k <= j; k++)
			{
				memo[j][i] += memo[j - k][i - 1];
				memo[j][i] %= 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일 프로젝트 - 89 day