백준 합분해 2 13707 (c++)

문제

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

13707번: 합분해 2

---

오랜만에 c++로 문제 풀려고 풀어봤다. dp로 풀었기 때문에 점화식만 구하면 쉽게 풀 수 있는 문제였다. 재귀로 풀어서 좀 오래 걸린 것도 있고, 다른 사람들 코드 보니까 더 간단하게 풀기도 했다.  점화식은 다음과 같다.

arr [k][n]으로 놓고 k개를 사용해서 n을 만들 수 있는 경우의 수를 구하면 된다. arr [k][n] = arr [k-1][0]+ arr [k-1][1].... arr [k-1][n] 이런 식으로 되는데 더하는 경우가 각각 마지막에 n, n-1, n-2..... 0을 사용했으니 그 수만큼 빼고 만들 수 있는 경우의 수들을 구해서 더한다. 냅색 문제랑 비슷한 거 같다. 또한 arr [k][n-1] 이 저 위에서 arr [k-1][n-1]까지의 모든 경우의 수를 더한 값이 되기 때문에 arr [k][n] 은 arr [k][n-1]에서 arr [k-1][n]만 더해주면 된다.

---

소스코드 

#include<bits/stdc++.h>
#define MOD 1000000000
using namespace std;

int N,K;
int cache[5001][5001];

int go(int n, int k){
	if(k==1)return 1;
	if(n==0)return 1;
	int &ret = cache[n][k];
	if(ret != -1) return ret;
	return ret = (go(n,k-1) + go(n-1,k))  %MOD;
}

int main(){
	
	memset(cache,-1,sizeof(cache));
	cin>>N>>K;
	cout<<go(N,K)<<endl;

	return 0;
}