백준] 2225 - 합분해

시간제한 : 2초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int N, K, mod = 1000000000;
	cin >> N >> K;
	vector<vector<long long> > dp(201, vector<long long>(201, 0));

	for (int i = 0; i <= N; i++)
		dp[1][i] = 1;
	for (int i = 2; i <= K; i++)
		for (int j = 0; j <= N; j++)
			for (int l = 0; l <= j; l++)
				dp[i][j] = (dp[i][j] + dp[i - 1][l]) % mod;

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

Tip

dp[i][j]는, 0부터 i까지의 정수를 j개 더해서 i를 만드는 경우의 수를 뜻하며, dp[1][i]는 모두 1로 볼 수 있다. 이 상황에서, dp[i][j]는 dp[i-1][0]부터 dp[i-1][j]까지의 합을 바탕으로 값을 구할 수 있다. 왜 그런지는 숫자를 나열해보면서 확인해보는 것이 좋다.