백준 [C++] 4811 알약

<조건 분석>

 

1. 알약이 최대 30개인데 반으로 쪼개 먹을 수도 있으니 최대 60번. 그러면 먹냐 안먹냐니까 최대 경우의 수가 2^60까지 될 수 있음.

 

2. 가능한 문자열의 경우의 수기에 경우의 수 덧셈으로 진행하면 될 것 같음.

 

<문제 해결 포인트>

 

1. 2^60은 말도 안되지만, 경우의 수 덧셈이라면 얘기가 다름.

 

2. 재귀로 경우의 수를 돌면서 메모제이션을 진행하면 충분히 가능할 수 있음.

 

3. 알약 한 조각을 꺼내면 반 조각 갯수를 올리고, 만약 반 조각을 먹는다면 한 조각 갯수를 안 내리면 됨.

 

#include <bits/stdc++.h>
using namespace std;

int n;
long long dp[40][40];

long long go (int day, int half)
{
    if (day <= 0 && half <= 0) return 1; // 알약 모두 없음

    long long& ret = dp[day][half];
    if (ret) return ret;
    
    if (day > 0)
    {
        if (half <= 0) // 알약 한 조각은 있는데 반 조각은 없음
        {
            ret += go(day - 1, half + 1);
        }
        else // 알약 한 조각도 있고 반 조각도 있음
        {
            ret += go(day - 1, half + 1) + go(day, half - 1);
        }
    }
    else
    {
        if (half > 0) // 알약 한 조각은 없는데 반 조각은 있음
        {
            ret += go(day, half - 1);
        }
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    while (true)
    {
        cin >> n;
        if (n == 0) break;

        memset(dp, 0, sizeof(dp));

        cout << go(n, 0) << "\n";
    }

    return 0;

}