[백준] 2225 합분해

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

2225번: 합분해

동적계획법으로 풀 수 있다.

아래 표 dp의 k행 n열은 숫자 k개를 가지고 n을 만들 수 있는 경우의 수이다.

3행 4열을 예로 들면

dp[3][4]는 3가지 수로 4를 만들 수 있는 방법의 개수인데 4는 0+4, 1+3, 2+2, 3+1, 4+0으로 나타낼 수 있다.

그런데 3행을 채울 당시에는 2행까지만 채워있으니 2행까지 구해놓은 것들을 가지고 3행을 구하면 된다.

 

0+4는 dp[1][0]*dp[2][4]로 표현 가능하고

(dp[1][0]은 1가지 수로 0을 만들 수 있는 방법의 개수, dp[2][4]는 2가지 수로 4를 만들 수 있는 방법의 개수)

 

1+3은 dp[1][1]*dp[2][3]으로 표현 가능하고

(dp[1][1]은 1가지 수로 1을 만들 수 있는 방법의 개수, dp[2][3]은 2가지 수로 3을 만들 수 있는 방법의 개수)

 

2+2는 dp[1][2]*dp[2][2]로 표현 가능하고

(dp[1][2]는 1가지 수로 2를 만들 수 있는 방법의 개수, dp[2][2]는 2가지 수로 2를 만들 수 있는 방법의 개수)

 

3+1은 dp[1][3]*dp[2][1]으로 표현 가능하고

(dp[1][3]은 1가지 수로 3을 만들 수 있는 방법의 개수, dp[2][1]는 2가지 수로 1을 만들 수 있는 방법의 개수)

 

4+0은 dp[1][4]*dp[2][0]으로 표현 가능하다.

(dp[1][4]는 1가지 수로 4를 만들 수 있는 방법의 개수, dp[2][0]는 2가지 수로 0를 만들 수 있는 방법의 개수)

 

즉, dp[3][4] = dp[1][0]*dp[2][4] + dp[1][1]*dp[2][3] + dp[1][2]*dp[2][2] + dp[1][3]*dp[2][1] + dp[1][4]*dp[2][0] 이다.

그런데 1행 즉 K가 1일 때에는 항상 값이 1이므로 1행의 1은 굳이 안 곱해줘도 된다.

따라서  dp[3][4] = dp[2][4] + dp[2][3] + dp[2][2] + dp[2][1] + dp[2][0] 이다.

 

점화식은 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + dp[i - 1][j - 2] + dp[i - 1][j - 3] + ... + dp[i - 1][0] 으로 표현할 수 있다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> dp(k + 1, vector<int>(n + 1));
	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= k; i++) {
		dp[i][0] = 1;
	}
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (int c = 0; c <= j; c++) {
				dp[i][j] = (dp[i][j] + dp[i - 1][c]) % 1000000000;
			}
		}
	}
	cout << dp[k][n];
	return 0;
}

오버플로우가 나지 않게 중간중간 1000000000으로 나눠줘야 한다.

이 코드를 제출하니 12ms가 나왔다.

 

다음은 개선된 코드이다.

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> dp(n + 1, 1);
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
				dp[j] = (dp[j - 1] + dp[j]) % 1000000000;
		}
	}
	cout << dp[n];
	return 0;
}

이렇게 일차원 배열로도 풀 수 있다.

여기에서 쓰는 점화식은 더 간단하다.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다. 그런데 이것을 일차원 배열로 바꾼 코드이다.

이 방법으로 제출하니 0ms가 걸렸다.