[C++] 백준 2225번 합분해

 

다이나믹 프로그래밍 문제입니다.

 

각 수마다 x개의 수로 구할 수 있는 경우의 수를 구합니다.

 

1. 1개로 구할 수 있는 경우의 수는 모두 1입니다.

for (int i = 0; i <= N; ++i) {
	memo[1][i] = 1;
}

 

2. x개로 구할 수 있는 경우의 수는 숫자가 n일 때

   x-1의 1의 경우의 수 ~ x-1의 n의 경우의 수를 모두 더한 값입니다.

for (int i = 2; i <= K; ++i) {
	for (int j = 0; j <= N; ++j) {
		for (int l = 0; l <= j; ++l) {
			memo[i][j] += memo[i - 1][l];
 		}
 	}
}

 

 

 

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

int main(int argc, char *argv[])
{
	int N;
	int K;
	int mod = 1000000000;
	int memo[210][210];
	memset(memo, 0, sizeof(memo));

	cin >> N;
	cin >> K;

	for (int i = 0; i <= N; ++i) {
		memo[1][i] = 1;
	}

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

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

	return 0;
}