[Algorithm]Baekjoon 4811번 :: 알약

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

4811번: 알약

 
 
using namespace std;
 
int n;
long long dp[31][31] = { 0 };
 
long long DFS(int w, int h)
{
    if (h == -1) return 0;
    if (w == 0) return 1;
    if (dp[w][h]) return dp[w][h];
 
    return dp[w][h] = DFS(w - 1,h + 1) + DFS(w,h-1);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    dp[30][0] = DFS(30, 0);
 
    while (1)
    {
        cin >> n;
 
        if (n == 0) break;
 
        printf("%lld\n", dp[n][0]);
    }
}

 

아직 나에게 DP는 어렵다..

 

한개짜리를 선택한날은 W라 표시하고 반개짜리를 선택한날은 H라 표시한다.

이 때, 알약이 N개 주어졌을 때 만들 수 있는 모든 문자열의 개수를 구하시오..라는 문제이다.

 

n개의 알약이 주어졌을 때, 할아버지는 한개짜리를 선택하거나 반개짜리를 선택한다.

한개짜리를 선택하면 그것을 반으로 쪼개서 반을 먹고 다시 병에 넣는다.

반개짜리를 선택하면 그냥 그대로 먹는다.

 

이걸 Top-Down방식으로 표현한 코드가 다음과 같다.

dp[w][h] = DFS(w-1,h+1) + DFS(w,h-1) 

 

한개짜리를 먹는다면

   -> 한개짜리개수인 w를 -1하고, 반을 먹고 반을 다시 병에 넣었으니 h+1. 그래서 DFS(w-1,h+1)

 

반개짜리를 먹는다면

   -> 한개짜리개수인 w는 그대로 냅두고, 반개짜리인 h를 -1. 그래서 DFS(w,h-1)

 

매 순간마다 한개짜리를 먹을지 반개짜리를 먹을지 선택지 2개가 주어지기 때문에 두 DFS값을 더한게 정답이다.

 

탐색을 진행하다 w가 0개가 된다면, 즉 더이상 한개짜리알약이 없고 병에 죄다 반개짜리만 있다면 그냥 H만 쭉 붙여버리면 되기때문에 탐색은 종료다. 그러므로 1을 리턴한다.

h가 -1개가 된다면 더이상 먹을 반개짜리가 없기 때문에 0을 리턴한다. 더이상 먹을 반개짜리가 없다면, 해당 탐색은 더할필요없고 다른 탐색에서 한개짜리를 먹음으로써 반개짜리를 만들어야 한다.