[BOJ 4811] 알약

- 문제 요약

 

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

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

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

 

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

 

(입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.)

 

 

- 알고리즘 정리

 

dp[a][b] = 한 조각 알약의 개수가 a, 반 조각 알약의 개수가 b일 때, 가능한 서로 다른 문자열의 개수

 

위와 같이 DP 테이블 정의를 해두고, 재귀로 구현해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 61
typedef long long ll;
int n;
ll dp[MAX][MAX];

ll f(int a,int b){
	if(!a){
		return 1;
	}
	ll &ret=dp[a][b];
	if(ret!=-1){
		return ret;
	}
	ret=0;
	if(a>0){
		ret+=f(a-1,b+1);
	}
	if(b>0){
		ret+=f(a,b-1);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	while(true){
		cin>>n;
		if(n==0){
			break;
		}
		memset(dp,-1,sizeof(dp));
		cout<<f(n-1,1)<<endl;
	}
}

코드 제출 결과