만약에 온전한 알약을 먹었다면 다음날은 온전한 알약은 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;
}