[2225번] 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

 

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

 

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

접근

DP(Dynamic programming)

dp[n][k] = 정수 n을 n보다 작거나 같은 k개의 정수로 만들 수 있는 경우의 수

 

ex> n = 20, k = 2일 때

k = 0일 경우 X

k = 1일 경우

    dp[0][1] = 1, dp[1][1] = 1, dp[2][1] = 1,  ···  dp[20][1] = 1

    → 정수 n을 n보다 작거나 같은 1개의 정수로 만들 수 있는 경우의 수는 모두 

        1 (정수 n) 이다.

k = 2일 경우

    dp[0][2] = 1

 

    dp[1][2] = (0, 1), (1, 0)                        →  dp[0][1] + dp[1][1]

 

    dp[2][2] = (0, 2), (1, 1), (2, 0)              →  dp[0][1] + dp[1][1] + dp[2][1]

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

 

    dp[3][2] = (0, 3), (1, 2), (2, 1), (3, 0)    →  dp[0][1] + dp[1][1] + dp[2][1] + dp[3][1]

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

 

 ··· 

 

+) n = 0일 경우

    dp[0][0] = 1, dp[0][1] = 1, dp[0][2] = 1,  ···  dp[0][20] = 1

    → 정수 0을 0보다 작거나 같은 1개의 정수로 만들 수 있는 경우의 수는 모두

        1 (정수 0) 이다.

 

따라서, 점화식은 dp[n][k] = dp[n- 1][k] + dp[n][k - 1] 이다

 

코드

 

점화식 코드

for (int k = 1; k <= K; k++) {
	for (int n = 0; n <= N; n++) {
		if (k == 1 || n == 0) {
			dp[n][k] = 1;
			continue;
		}
		dp[n][k] = (dp[n][k - 1] + dp[n - 1][k]) % mod;
	}
}

 

전체 소스 코드

#include <iostream>

using namespace std;

int main() {
	int N, K;
	int dp[201][201] = {0,};
	const int mod = 1000000000;

	cin >> N >> K;
	
	for (int k = 1; k <= K; k++) {
		for (int n = 0; n <= N; n++) {
			if (k == 1 || n == 0) {
				dp[n][k] = 1;
				continue;
			}
			dp[n][k] = (dp[n][k - 1] + dp[n - 1][k]) % mod;
		}
	}
	
	cout << dp[N][K] << endl;

}