[BOJ] 4811 알약 C++

개요

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

4811번: 알약

골드5 짜리 DP문제다.

풀이

W는 일반 알약, H가 반쪽짜리 알약이다.

2차원 배열의 형태로 생각을 해보았는데, 보면 반복적인 형태가 보인다.

W와 H가 공존할 때 경우의 수가 증가하는 규칙이 있다.

위 과정을 통해 점화식을 구했고 재귀(Top-Down)로 구현했다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
long long dp[31][31];

long long GetCount(int w, int h)
{
	if(w<0 || h<0) return 0;
	if(dp[w][h]!=0) return dp[w][h];
	dp[w][h] = GetCount(w-1, h+1) + GetCount(w, h-1);
	return dp[w][h];
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	for(int i=1; i<31; i++)
		dp[0][i] = 1;
	GetCount(30,0);

	while(true)
	{
		cin >> N;
		if(N==0) break;
		cout << dp[N][0] << "\n";
	}
}