[DP (동적 프로그래밍) / BOJ 4811 / C++] 알약

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

4811번: 알약

 

이번 문제도 전형적인 dp문제. 상태값을 잘 생각해보면 2가지.

병안에 한조각 짜리 개수와, 병안에 반조각짜리 개수를 기준으로 세가면 끝.

 

종료 조건은 병안에 한조각짜리도, 반조각짜리도 없으면 즉시 종료!

W,H에 흔들리지 말고 직접 경우의 수를 완전탐색 방식으로 몇개만 세봐도 간단하게 해결된다

 

현재 상태에서 1번 선택 혹은 2번 선택을 이어나간다. 즉 종료조건에 도달할때는 그 경로가 유일하다!!

 

 

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

ll N, dp[31][61];

ll go(ll n1, ll n2){ // n1 : 병안에 한조각짜리 개수 n2 : 병안에 반조각짜리 개수
    if(n1 < 0 || n2 < 0) return 0;
    if(n2==0 && n1==0) return 1;
    
    ll &mid = dp[n1][n2];
    if(mid!=-1) return mid;
    
    // 한조각 꺼내고 쪼개서 먹기 vs 반조각먹기
    ll oneAndHalf = go(n1-1, n2+1);
    ll onlyHalf = go(n1, n2-1);
    
    mid = oneAndHalf + onlyHalf;
    
    return mid;
}



int main(){
    
    memset(dp, -1, sizeof(dp));
    
    while(true){
        cin >> N;
        if(N==0) break;
        cout << go(N, 0) << '\n';
    }
    
    return 0;
}