[2225번] 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

[2225번] 합분해

 

0부터 N까지의 정수 중 K개를 더한 값이 N이 되는 경우의 수를 구하라.

 

덧셈의 순서가 바뀐 경우는 다른 경우에 해당하고, 한 개의 수를 여러 번 사용 가능하다.

 

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력하라

 

만약 N = 20, K = 1 일 때, 0 ~ 20까지의 정수 중 1개를 더한 값이 20이 되는 경우의 수는 1이다.

 

이를 dp로 표현하기 위해 2차원 배열을 정의하면

 

dp[N][K] : 정수 N을 K개의 정수의 합으로 만들 수 있는 경우의 수

 

N = 20, K = 1

dp[0][1] = 1 -> (0) 

dp[1][1] = 1 -> (1)

dp[2][1] = 1 -> (2)

...

dp[19][1] = 1 -> (19)

dp[20][1] = 1 -> (20)

 

N = 20, K = 2 일 때 dp[n][k]는

 

N = 20, K = 2

dp[0][2] = 1 -> (0, 0)

dp[1][2] = 2 -> (0, 1), (1, 0)

dp[2][2] = 3 -> (0, 2), (1, 1), (2, 0)

dp[3][2] = 4 -> (0, 3), (1, 2), (2, 1), (3, 0)

...

 

dp[0][2] = 1

 

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

           = (dp[0][1]에 정수 하나를 더하여 1이 나오는 경우)

           + (dp[1][1]에 정수 하나를 더하여 1이 나오는 경우)

 

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

           = (dp[0][1]에 정수 하나를 더하여 2가 나오는 경우)

           + (dp[1][1]에 정수 하나를 더하여 2가 나오는 경우)

           + (dp[2][1]에 정수 하나를 더하여 2가 나오는 경우)

 

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

           = (dp[0][1]에 정수 하나를 더하여 3이 나오는 경우)

           + (dp[1][1]에 정수 하나를 더하여 3이 나오는 경우)

           + (dp[2][1]에 정수 하나를 더하여 3이 나오는 경우)

           + (dp[3][1]에 정수 하나를 더하여 3이 나오는 경우)

 

....

 

위처럼 dp[n][2]를 구할 수 있다.

 

이때, dp[2][2] = dp[1][2] + dp[2][1], dp[3][2] = dp[2][2] + dp[3][1] 으로 표현 가능하다

 

이를 통해 점화식을 구하면 dp[n][k] = dp[n-1][k] + dp[n][k-1] 이다.

for(int i = 0; i <= n; i++) {
	for (int j = 2; j <= k; j++) {
		if (i == 0) {
			dp[i][j] = 1;
			continue;
		}
		dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
	}
}

 

[전체소스코드]

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
	int n = 0;
	int k = 0;
	int dp[201][201] = { 0 };
	const int mod = 1000000000;

	cin >> n >> k;

	for (int i = 0; i <= n; i++) {
		dp[i][1] = 1;
	}

	for(int i = 0; i <= n; i++) {
		for (int j = 2; j <= k; j++) {
			if (i == 0) {
				dp[i][j] = 1;
				continue;
			}
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}

	cout << dp[n][k] << endl;

	return 0;
}