백준 2225: 합분해

문제 요약

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

문제 분류

• 수학
• 다이나믹 프로그래밍

문제 풀이

큰 문제가 작은 문제를 포함하고 있는 전형적인 DP문제이다. N에는 0이 포함되므로, N에서 K개를 사용하여 구한 수가 N이 되는 경우는 0~N에서 K-1개를 사용하여 구한 경우를 누적한 것과 같다. 즉

dp[N][K] += sol(N - i, K - 1) 이고, i의 범위는 0~N이 된다. 해당 결과를 누적하는 점화식이라 할 수 있겠다.

단, 배열에는 1,000,000,000으로 나눈 나머지를 저장하여 그 값을 반환하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

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

int sol(int num, int cnt) {
	if (num == 0) return 1;
	if (cnt == 0) return 0;
	if (dp[num][cnt] != -1) return dp[num][cnt];
	dp[num][cnt] = 0;
	for (int i = 0; i <= num; i++) {
		dp[num][cnt] += sol(num - i, cnt - 1);
		dp[num][cnt] %= 1000000000;
	}
	return dp[num][cnt];
}

int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%d%d", &n, &k);
	cout << sol(n, k);
}