[백준 BOJ][C++]2225번 합분해 풀이: DP

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

2225번: 합분해

 

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

 dp부터 설정해야겠죠?

 

 dp[i][j] 는 i 개의 숫자의 합이 j 가 되는 경우의 수를 나타냅니다. 

 

 초깃값으로는 dp[1][j]는 모두 1이 되겠죠?

 

 dp[2][j] 부터 보겠습니다. 각 색깔이 다음 단계에서 어떻게 쓰이는지 봐주세요!

	모든 경우	경우의 수
dp[2][0]	0+0	1
dp[2][1]	0+1 1+0	2
dp[2][2]	0+2 1+1 0+1	3

 

dp[3][j] 는 어떻게 될까요?

	모든 경우	경우의 수
dp[3][0]	0+0+0	1
dp[3][1]	0+0+1 0+1+0 1+0+0	3
dp[3][2]	0+2+0 0+0+2 0+1+1 1+1+0 1+0+1 2+0+0	6

 

색상으로 나누어 보니까 이해가 더 잘가시죠 ㅎㅎ

 

dp[3][0] = dp[2][0],

dp[3][1] = dp[2][0]+dp[2][1]

dp[3][2] = dp[2][0]+dp[2][1]+dp[2][2]

 

로 나타낼 수 있습니다. 

 

 위 표에서 알 수 있듯이 점화식은 dp[i][j] = dp[i-1][0]+...+dp[i-1][j] 가 됩니다. 

 

위 과정을 dp[k][n]까지 반복하면 됩니다. 

 

다음은 전체코드입니다. 

#include<iostream>
#include <string>
#include <vector>
#include<queue>

using namespace std;

#define mod 1000000000
long long dp[201][201] = { 0, };

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;

	cin >> n >> k;

	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 s = 0; s <= j; s++) {
				dp[i][j] += dp[i - 1][s];
			}
			dp[i][j] %= mod;
		}
	}

	cout << dp[k][n];

	return 0;
}