[백준 2225] 합분해

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

2225번: 합분해

---

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

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구해야 한다.

 

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. => 이부분에서 dp 를 활용해야 한다는 것을 확인할 수 있다.

 

다음과 같은 시뮬레이션으로 dp를 유추해보도록 한다.

 

n=20, k=1 인 경우

• 합이 20일 경우 => 20 / 1개 , dp[1][20] = 1
• 합이 19일 경우 => 19 / 1개 , dp[1][19] = 1
• ...
• 합이 0일 경우 => 0 / 1개 , dp[1][0] = 1

k=1 인 경우 0~n까지의 모든 dp 값은 1임을 알 수 있다.

 

n=20, k=2 인 경우

• 합이 20일 경우 => 0 + (20), 1 + (19), ... , 20 + (0) / 21개 , dp[2][20]=21
• 합이 19일 경우 => 0 + (19), 1 + (18), ... , 19 + (0) / 20개 , dp[2][19]=20
• ...
• 합이 0일 경우 => 0 + (0) / 1개 , dp[2][0] = 1

n=20, k=3 인 경우 (여기서 부터 확실한 규칙성을 발견)

• 합이 20일 경우 => 0 + ( k=2 일때의 합이 20이 되는 경우 ), 1 + ( k=2 일때의 합이 19가 되는 경우), ... , 20 + ( k=2 일때의 합이 0이 되는 경우) / dp[3][20] = dp[2][20] + dp[2][19] + ... + dp[2][0] = (21 + 20 + ... + 1) 개
• 합이 19일 경우 => 0 + ( k=2 일때의 합이 19가 되는 경우 ), 1 + ( k=2 일때의 합이 18가 되는 경우), ... , 19 + ( k=2 일때의 합이 0이 되는 경우) / dp[3][19] = dp[2][19] + dp[2][18] + ... + dp[2][0] = (20 + 19 + ... + 1) 개
• ...
• 합이 0일 경우 => 0 + ( k=2 일때의 합이 0이 되는 경우 ) / dp[3][0] = dp[2][0] = 1 개

...

즉 dp[1][0~n] = 1로 초기화 해주고 위 규칙을 통해 다음과 같은 식을 유도할 수 있다.

 

dp[n][k] = dp[k-1][n] + dp[k-1][n-1] + ... + dp[k-1][0]

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

long long dp[201][201];
long long result;

void solve(int n,int k) {
	for (int i = 0; i <= n; i++) dp[1][i] = 1;
	for (int i = 2; i <= k; i++) {
		for (int j = n; j >= 0; j--) {
			for (int t = 0; t <= j; t++) {
				dp[i][j] = (dp[i][j] + dp[i - 1][t]) % 1000000000;
			}
		}
	}
	cout << dp[k][n];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;
	solve(n, k);

	return 0;
}