문제 풀이

Top-Down DP 연습을 위한 문제

DP배열은 DP[W][H]로 W,H는 각각 남은 한 조각짜리 알약, 반 조각짜리 알약이다.

n개의 한 조각짜리 알약으로 시작해서, 한 조각 짜리를 반으로 쪼갤지, 반 조각 짜리를 먹을지 나눈다.

한 조각짜리를 모두 먹었다면 반 조각짜리 밖에 먹을 수 없으므로 1을 return 해준다.

문제 링크

boj/4811

소스코드

PS/4811.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include<memory.h>
using namespace std;


long long dp[31][61];

long long solution(int idx, int cnt);
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	while (1)
	{
		memset(dp, -1, sizeof(dp));
		int n;
		cin >> n;
		if (n == 0)
			break;
		cout << solution(n, 0) << '\n';
	}


}
long long solution(int w, int h)
{
	if (w == 0)
		return 1;
	if (dp[w][h] != -1)
		return dp[w][h];
	dp[w][h] = 0;
	dp[w][h] += solution(w - 1, h + 1);
	if (h >= 1)
		dp[w][h] += solution(w, h - 1);
	return dp[w][h];
}