[백준 4811] 알약 C++

4811번: 알약

다이나믹 프로그래밍

---

1. 문제 해결 아이디어

dp[한 조각 알약의 개수][반 조각 알약의 개수]를 통해서 메모이제이션을 해주면 쉽게 풀린다.

한 조각 알약이 0개라면 앞으로 반 조각을 먹는 경우밖에 없으므로 return 1을 하는 기저 조건이 된다.

 

재귀 함수 내부에서는 한 조각 알약의 개수가 0보다 크면 한 조각을 빼고 반 조각을 추가해서 재귀 호출을 하고

마찬가지로 반 조각 알약의 개수가 0보다 크면 반 조각만 빼고 재귀호출을 하는 식으로 구현을 했다.

---

2. 코드

top down 방식

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N;
long long dp[61][61];
 
long long solve(int one, int half){
    if(!one) return 1;
    
    long long &ret = dp[one][half];
    if(ret != -1) return ret;
    
    ret = 0;
    
    if(one > 0){
        // 한 조각 약을 먹고 반 조각을 추가
        ret += solve(one-1, half+1);
    }
    if(half > 0){
        // 반 조각을 먹는다
        ret += solve(one, half-1);
    }
    
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
    while(N){
        memset(dp, -1, sizeof(dp));
        cout << solve(N-1, 1) << "\n";
        cin >> N;
    }
    
    return 0;
}