백준 4811번 알약 c++ 풀이

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

예제 입력 1 복사

6
1
4
2
3
30
0

예제 출력 1 복사

132
1
14
2
5
3814986502092304

 

 

DP 문제이고, dfs로 완전탐색을 구현한 후에 중복되는 부분을 DP를 통해서 메모이제이션을 해 주면 되는 문제이다.

DP 문제를 쉽게 풀고 싶으면 먼저 완전탐색으로 돌아가는 경우를 만들고 중복되는 부분을 DP로 만들어주면 되는데 이 문제는 전형적인 그런 루트를 따르는 문제였다.

 

- c++ 풀이

#include <bits/stdc++.h>

#define ll long long int

using namespace std;

ll dp[31][31];

ll dfs(int w, int h) {

    if (h == -1) return 0;
    if (w == 0)return 1;

    ll &ret = dp[w][h];
    if (ret) return dp[w][h];
    ret = dfs(w - 1, h + 1) + dfs(w, h - 1);
    return ret;

}


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

    while (1) {
        int w;
        cin >> w;
        if (w == 0)return 0;
        cout << dfs(w, 0) << endl;
    }

    return 0;
}