2225(합분해)

난이도: 골드 5

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

문제

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

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

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

풀이

N = 4이면서 K = 1일 때는 항상 경우가 1가지 밖에 없고,

K = 2라고 가정하면,

경우의 수는 {0 + 4}, {1 + 3}, {2 + 2}, {3 + 1}, {4 + 0} 이렇게 5가지의 경우가 나오게 됩니다.

K = 3이라고 가정한다면,

{0 + 0 + 4}, {0 + 1 + 3}, {0 + 2 + 2}, {0 + 3 + 1}, {0 + 4 + 0},

{1 + 0 + 3}, {1 + 1 + 2}, {1 + 2 + 1}, {1 + 3 + 0},

{2 + 0 + 2}, {2 + 1 + 1}, {2 + 2 + 0},

{3 + 0 + 1}, {3 + 1 + 0},

{4 + 0 + 0}

이와 같은 패턴으로 15가지의 경우가 나오게 됩니다.

 

이 때 패턴을 찾아보면,

K = 3일 때 뒷 부분 정수 2개의 합이 K =2일 때 N = 0 ~ 4를 만드는 경우의 수와 동일하다는 것을 알 수 있습니다.

즉, 

{0 + 0 + 4}, {0 + 1 + 3}, {0 + 2 + 2}, {0 + 3 + 1}, {0 + 4 + 0},    >> K = 2, N = 4 (5가지)

{1 + 0 + 3}, {1 + 1 + 2}, {1 + 2 + 1}, {1 + 3 + 0},  >> K = 2, N = 3 (4가지)

{2 + 0 + 2}, {2 + 1 + 1}, {2 + 2 + 0},  >> K = 2, N = 2 (3가지)

{3 + 0 + 1}, {3 + 1 + 0},  >> K = 2, N = 1 (2가지)

{4 + 0 + 0}  >> K = 2, N = 0 (1가지)

 따라서, 이를 이용해 점화식을 구할 수 있고 dp를 이용해야 한다는 것을 알 수 있습니다.

#include <iostream>
using namespace std;
#define MAX 201

const int MOD = 1000000000;

int N, K;
int dp[MAX][MAX] = { 0 };	// dp[K][N]

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

	for (int i = 0; i <= N; i++)
		dp[1][i] = 1;	// K = 1일 때는 무조건 1가지 경우 밖에 없음

	for (int k = 2; k <= K; k++)
	{
		for (int n = 0; n <= N; n++)
		{
			for (int i = 0; i <= n; i++)
				dp[k][n] = (dp[k][n] + dp[k - 1][i]) % MOD;
		}
	}

	cout << dp[K][N] << endl;
}