[백준 4811] 알약 C++

문제

백준 4811 알약 C++

4811번: 알약

풀이

Top-down 방식의 dp를 이용한다.

 

알약을 꺼낼 때, 경우의 수는 다음과 같다. (반 개 짜리는 h, 한 개 짜리는 w로 지칭한다.)

dp[w][h]는 한 개 짜리가 w, 반 개 짜리가 h만큼 있는 경우 알약을 먹을 수 있는 가짓 수를 뜻한다.

 

1. w != 0, h != 0인 경우

1-1. w를 먹는다. h가 한 개 늘어나고 w는 1 줄어든다.

그 후에 dp[w-1][h+1] 만큼의 경우의 수가 생긴다.

 

1-2. h를 먹는다. h가 한 개 줄어들고 w 개수는 변함 없다.

그 후에 dp[w][h-1] 만큼의 경우의 수가 생긴다.

 

2. h = 0 이고, w != 0인 경우.

w를 먹는다. h가 한 개 늘어나고 w는 1 줄어든다.

즉 dp[w][0] = dp[w-1][1]이다.

 

3. w = 0 인 경우

그 다음 날 부터는 h만 계속 먹으면 된다. 경우의 수는 1이다.

 

일반화 하면 아래 코드와 같다.

소스 코드

#include <iostream>
#include <cstring>
using namespace std;
 
long long dp[31][31];
 
long long Sol(int w, int h)
{
    // 반 알 밖에 없으면 경우의 수는 1가지
    if (w == 0)
        return 1;
 
    long long& result = dp[w][h];
 
    // 이미 값이 메모리제이션 되어 있는 경우 그 값 리턴
    if (result != -1)
        return result;
 
    // w != 0인 경우 w를 먹는 방법 추가
    result = Sol(w - 1, h + 1);
 
    // h != 0인 경우 h를 먹는 방법 추가
    if (h > 0)
        result += Sol(w, h - 1);
 
    return result;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    // -1로 초기화
    memset(dp, -1, sizeof(dp));
 
    int input = 0;
 
    while (1)
    {
        cin >> input;
 
        if (input == 0)
            break;
 
        cout << Sol(input, 0) << "\n";
    }
 
    return 0;
}