백준 4811번 알약 ( C++ )

문제

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

 

해설

dp로 풀어야 하는 문제임은 빠르게 알 수 있으나 어떻게 풀지 조금 걸린 문제

온전한 알약과 반만남은 알약을 기준으로 문제를 해결

 

코드

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
typedef long long ll;
 
int n;
ll dp[34][34];
 
ll go(int full, int half){
  if(full == 0 && half ==0) return 1;
  ll &ret = dp[full][half];
 
  if(ret) return ret;
  if(half > 0) ret += go(full,half-1);
  if(full>0) ret += go(full-1,half+1);
  return ret;
}
 
int main(){
  while(true){
    cin >> n;
    if(n == 0) return 0;
 
    cout << go(n,0) << "\n";
  }
}