[BOJ] (C++) 2225 합분해

전형적인 2차원 DP문제이며 자주 보였던 유형이다.

오랜만에 풀어서 시간이 좀 걸리긴 했지만 점화식을 세워 3차원 반복문으로 풀었다.

문제링크 : 2225번: 합분해 (acmicpc.net)

#include <iostream>
#include <vector>

using namespace std;

#define DIV 1000000000

int main() {

	int N, K;
	cin >> N >> K;

	vector<vector<int>> DP(K + 1, vector<int>(N + 1, 0));
	DP[0][0] = 1;

	for(int i = 1; i <= K; i++)
		for (int j = 0; j <= N; j++) {
			for (int k = 0; k <= j; k++)
			{
				DP[i][j] += DP[i - 1][j - k];
				DP[i][j] %= DIV;
			}
		}

	cout << DP[K][N] << endl;

	return 0;
}