BOJ 2225 - 합분해

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

문제의 예시로 n=20, k=2일 때 나올 수 있는 경우의 수는

 0 + 20

 1 + 19

 2 + 18

   ...

19 + 1

20 + 0

로 총 21개이다.

풀이

n=20이고 k=3이라면, 경우의 수는 아래와 같은 모양으로 전개된다.

(n=20, k=3) =

   (n=20, k=2)

+ (n=19, k=2)

+ ...

+ (n=1, k=2)

+ (n=0, k=2)

3개의 수를 n=20 내에서 고르는 경우의 수 = 

   첫 번째 수로 0을 사용하고, 나머지 2개의 수를 n=20 내에서 고르는 경우의 수

+ 첫 번째 수로 1을 사용하고, 나머지 2개의 수를 n=19 내에서 고르는 경우의 수

+ ....

작은 문제로 쪼개어 해결이 가능하다. dp 테이블을 두고 메모이제이션했다.

k=1이면 가능한 경우는 n을 선택하는 1가지 밖에 없으므로 f(n, 1) = 1 이다.

코드

	#include <cstdio>
	#include <cstring>
	const int MOD = 1e9;
	int dp[201][201];
	int f(int n, int k) {
	if (k == 1) return 1;
	int& ret = dp[n][k];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i <= n; ++i) {
	ret = (ret + f(n - i, k - 1)) % MOD;
	}
	return ret;
	}
	int main() {
	memset(dp, -1, sizeof(dp));
	int n, k;
	scanf("%d %d", &n, &k);
	printf("%d\n", f(n, k));
	return 0;
	}

view raw boj-2225.cpp hosted with ❤ by GitHub