[백준/BOJ] 백준 2225번 : 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

덧셈의 순서가 바뀐 경우도 다른 경우로 세고, 수를 여러 번 쓸 수 도 있으므로 숫자를 더해가는 경우(기저 사례가 아닌 경우)일 때 숫자 0부터 n까지를 확인하여 해당 수를 더한 경우를 확인한다. cache[sum][num]은 현재까지 합이 sum이고 숫자 num개를 사용했을 때 계산한 적이 있다면 중복해서 계산하지 않고 계산했던 값을 사용한다.

 

코드

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

int n, k;
int cache[201][201];

//초기화
void Pre()
{
	for (int i = 0; i < 201; i++)
		for (int j = 0; j < 201; j++)
			cache[i][j] = -1;
}

int Solve(int sum, int num)
{
	//k개를 더했을때
	if (num == k)
	{
		//그 합이 n일때
		if (sum == n)
			return 1;

		else
			return 0;
	}

	//합이 n보다 클때
	if (sum > n)
		return 0;

	//개수가 k보다 클때
	if (num > k)
		return 0;

	int& ret = cache[sum][num];

	if (ret != -1)
		return ret;

	ret = 0;

	//숫자 0부터 n까지 확인
	for (int i = 0; i <= n; i++)
	{
		ret += Solve(sum + i, num + 1);
		ret %= 1000000000;
	}

	return ret;
}

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

	cin >> n >> k;

	Pre();

	cout << Solve(0, 0);

	return 0;
}