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

 

[예제 입력 1]

20 2

[예제 출력 1]

21

---

풀이

 코드의 기본 알고리즘은 당연히 완전 탐색을 기본으로 한다. 기저 조건으로는 횟수를 모두 채웠고 합이 N과 같다면 1을 반환, 그게 아니라면 0을 반환한다. 아니면 아직 탐색 중이라면 0부터 남은 값(N - acc)까지 해당 함수를 재귀호출하여 acc+i, count+1을 넘겨 탐색을 진행한다.

 캐시 배열은 탐색 함수의 인자로 오는 acc와 count를 하나의 축으로 삼은 2차원 배열을 만들어, 해당 값을 저장하고 이를 반환하는 형태를 코드에 적용했다. 

유의할 점

 이 문제 또한 대개 캐시 배열 초기화에서도 통과가 갈렸는데, 초기화를 할 때 -1값을 넣어 해당 값이 현재 계산된 적이 있는 지 없는 지를 나누었다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<long long>> cache;

long long search(int N, int K, int acc, int count) {//탐색 함수
	long long result = 0;

	if (count == K)//횟수는 채운 경우
		if (acc == N)//N에 맞다면
			return 1;
		else//아니라면
			return 0;

	if (acc > N)//이미 넘어선 경우라면
		return 0;

	if (cache[acc][count] != -1)//캐시값 확인
		return cache[acc][count];

	for (int i = 0; i <= N - acc; i++)//0부터 N - acc까지
		result += search(N, K, acc + i, count + 1) % 1000000000;

	return cache[acc][count] = result % 1000000000;
}

int main() {
	int N, K;

	cin >> N >> K;

	for (int i = 0; i <= N; i++) {//캐시 배열 생성
		vector<long long> temp(K + 1, -1);
		cache.push_back(temp);
	}

	cout << search(N, K, 0, 0);

	return 0;
}

---

결과