백준 2225 합분해

 

0~N까지의 수를 K번 이용하여 N을 만드는 경우를 출력하는 문제입니다.

 

N,K가 모두 <= 200 이므로 dp를 이용하여 해결하면 됩니다.

 

저는 dp[i][j] --> j개의 숫자를 써서 i를 만드는 경우로 정의를 하였습니다.

 

숫자의 중복이 가능하므로 각 함수마다 0~N까지 숫자를 다돌려봐야 하므로 시간복잡도는

O(N^2*K) 정도가 되겠습니다.

 

아래는 코드입니다. 

 

 

#include <iostream>
#include <cstring>

#define MOD 1000000000
using namespace std;

long long dp[220][220];
int N, K;

long long sol(int k, int sum) {
	
	if (sum > N) return 0;
	if (K == k) {
		if (sum == N) return 1;
		else return 0;
	}

	long long &ret = dp[sum][k];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i <= N; i++) {
		ret += sol(k + 1, sum + i);
		ret %= MOD;
	}

	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	memset(dp, -1, sizeof(dp));
	
	cin >> N >> K;
	
	cout<<sol(0, 0);

	return 0;
}