백준 4811

백준 4811 : 알약

1. dp문제이다.
2. 온전한 알약을 a개, 반쪽짜리 알약을 b개 가지고 있다고 하자.

만약에 온전한 알약을 먹었다면 다음날은 온전한 알약은 a-1개, 반쪽짜리 알약은 b+1개가 될 것이다. (dp[a-1][b+1])

만약에 반쪽짜리 알약을 먹었다면 다음날은 온전한 알약은 a개, 반쪽짜리 알약은 b-1개가 될 것이다. (dp[a][b-1])

위 두개를 통합하면 dp[a][b] = dp[a-1][b+1] + dp[a][b-1] 가 된다.

쭉 진행하다 보면 a나 b가 0이 되는 경우가 생길 것이다.

1) a가 0이 된 경우
반쪽짜리 알약밖에 남지 않은 것이므로 남은 날 내내 반쪽짜리만 먹으면 된다. (dp[0][b]=0)

2) b가 0이 된 경우
a에서 하나 먹고, b를 1 증가시키면 된다. (dp[a][b] = dp[i-1][1])

처음에 주어지는 알약은 온전한 알약 N개가 주어지므로, 구하고자 하는 정답은 dp[N][0]이 된다.

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
long long dp[31][31];

void pro() {
	for(int i=0; i<31; i++) {
		for(int j=0; j<31; j++) {
			if(i==0) {
				dp[i][j]=1;
			}
			else if(j==0) {
				dp[i][j]=dp[i-1][1];
			}
			else {
				dp[i][j] = dp[i-1][j+1] + dp[i][j-1];
			}
		}
	}
}

int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	while(1) {
		cin>>n;
		if(n==0) break;
		
		pro();
		
		cout<<dp[n][0]<<'\n';
	}
	
	
	return 0;
}