[C/C++] 백준 - 17213번 : 과일 서리

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

17213번: 과일 서리

문제

민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. 지환이는 완벽한 범죄를 위하여 처음 생각한 개수 만큼만 훔치려고 한다. 이때 지환이가 훔칠 수 있는 경우의 수가 몇가지나 될 지 알아보자. 단, 모든 종류의 과일을 적어도 1개는 훔친다.

 

---

 

훔치려는 M개의 과일을 N개 종류의 과일에서 모든 종류의 과일을 적어도 1개씩 훔치는데 모든 경우의 수를 세어야한다. 백트래킹 조합이 해결법으로 떠올랐지만 같은 방법의 수가 겹치는 구간이 분명히 존재할 것이라고 생각하였다.

그래서 그러한 부분은 메모이제이션을 적용하여 완전탐색 + 메모이제이션 =>> 동적계획법으로 해결하였다.

 

메모이제이션은 [과일의 종류 인덱스][남은 과일의 수]로 하여도 메모리 내 충분히 통과가 가능하다.

단, 모든 종류의 과일을 적어도 1개는 훔쳐야하기 때문에 탑바텀 방식으로 훔칠 수 있는 과일의 개수가 0개가 되었는데도 아직 전체 N개의 과일을 훑지 못했다면 0을 반환하여 훔치는 것이 불가능하다는 것을 알려주었다.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define ENDL cout << endl

using namespace std;

int N, M;
int cache[10 + 1][30 + 1];

void input() {
	cin >> N;
	cin >> M;
}

int path(int index, int count) {
	if (!count) {
		if (index < N) return 0;
		return 1;
	}
	if (index == N) return 0;
	int& ret = cache[index][count];
	if (ret != -1) return ret;

	ret = 0;
	return ret += path(index, count - 1) + path(index + 1, count - 1);
}

int solution() {
	memset(cache, -1, sizeof(cache));
	return path(0, M);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}