[C/C++] 백준 - 4811번 : 알약

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

4811번: 알약

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

 

 

특정 N일 째에 가능한 경우의 수 -> 온전한 알약의 개수 / 반쪽 알약의 개수를 통해 생성할 수 있는 문자열의 개수(w의 개수, h의 개수)를 파악하여 메모이제이션 시켜준다. 온전히 문자열을 만들 수 있는 경우는 시작부터 2N일 때까지 이어나갈 수 있는 경우이며 이를 기저사례로 적용시켜주었다.

 

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

using namespace std;

int N;
ll cache[62][100][100];

ll func(int all, int half, int day, int w, int h) {
	if (day == 2*N) return 1;
	ll& ret = cache[day][w][h];
	if (ret != -1) return ret;

	ret = 0;
	if (all > 0) ret += func(all - 1, half + 1, day + 1, w+1, h);
	if (half > 0) ret += func(all, half - 1, day + 1, w, h+1);
	return ret;
}

void input() {
	while (1) {
		cin >> N;
		if (!N) break;
		memset(cache, -1, sizeof(cache));
		cout << func(N, 0, 0, 0, 0) << endl;
	}
}

int main() {
	fastio;
	input();

	return 0;
}