[2225] 합분해

https://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으로 나눈 나머지를 출력한다.

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int N,K;
vector<int> num;
long long cache[201][201];

long long getSum(int toPick, int sum){
	if(sum < 0){
		return 0;
	}
	
	if(toPick == 0){
		if(sum == 0){
			return 1;
		}
	
		return 0;
	}

	long long& ret = cache[sum][toPick];

	if(ret != -1){
		return ret % 1000000000;
	}

	ret = 0;
	for(int i=0; i<=N; ++i){
		ret += getSum(toPick-1, sum-num[i]) % 1000000000;
	}

	return ret % 1000000000;
}

int main(void){
	memset(cache, -1, sizeof(cache));
	
	cin >> N >> K;

	for(int i=0; i<=N; ++i){
		num.push_back(i);
	}

	cout << getSum(K, N) % 1000000000;
}

dp 문제이다.

이번 문제는 간단한 dp 문제라 재귀로 풀었다.

항상 강조하는게 재귀 dp 는 top to bottom이라 거꾸로 이해해서 풀어야 한다.

여기서도 sum을 N으로 두고 시작해 깎아 내리는 식으로 풀었다.

 

답을 몇으로 나누라는 문제들은 어짜피 (A+B) % N = A%N + B%N이기 때문에 용량 초과가 날거 같은 곳에 다 % N을 해주면 대충 맞는다.