알약

출처 : 백준 #4811

시간 제한	메모리 제한
1초	256MB

---

문제

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

---

풀이

생각 및 풀이 설명

• 다이나믹 프로그래밍으로 접근하였다.
  
  

• 매 단계(level)마다 glass_bottle에 담아서 알약을 하나 꺼내는 경우(W)와 반 개 꺼내는 경우(H)를 나누어 각각 계산하고, memoization을 위해 2차원 배열인 table에 이전 경우의 수를 가져와 더한다.

• 만약 table의 초기값인 0이 그대로 있는 상태라면 table의 값을 변경해줌과 동시에 temp라는 임시 glass_bottle에 담고 recursion 해준다.

• 만약 table의 값이 0이 아니라면, 그냥 table 계산만 하고 temp에는 넣지 않는다.

  • 이유는 동일한 루트의 중복 계산을 막기 위함이다.

python code

# 백준 4811번 알약
from sys import stdin
input = stdin.readline

def solution(n, glass_bottle, table):
    temp = []
    for W, H in glass_bottle:
        if (W, H) == (0, 0):
            print(table[W][H])
            return
        else:
            if W > 0:
                if table[W-1][H+1] == 0:
                    table[W-1][H+1] += table[W][H]
                    temp.append((W-1, H+1))
                else:
                    table[W-1][H+1] += table[W][H]
            if H > 0:
                if table[W][H-1] == 0:
                    table[W][H-1] += table[W][H]
                    temp.append((W, H-1))
                else:
                    table[W][H-1] += table[W][H]
    solution(n, temp, table)

result = []
while True:
    n = int(input())
    if n != 0:
        glass_bottle = [(n, 0)]
        table = [[0]*(n+1) for _ in range(n+1)]  # memoization table (2차원)
        table[n][0] = 1 # initialize
        result.append(solution(n, glass_bottle, table))
    else:
        break