백준: 4811 알약

문제

4811번: 알약

 

문제 풀이

  N개의 약이 담긴 병이 주어질 때, 첫째 날에는 약을 꺼내서 반 조각으로 나눈 후 반은 먹고 반은 다른 병에 넣는다. 그다음 날에는 약을 꺼내서 반 조각이면 먹고, 반 조각이 아니라면 반을 쪼개서 먹은 후 남은 것은 다른 병에 넣는다. 한 조각을 꺼낸날에는 W, 반 조각을 꺼낸 날에는 H일 때 2N일 후에 서로 다른 문자열의 개수를 반환하는 문제이다. 이는 DFS를 통해 반 조각이 남아있는 경우를 반영하여 호출하면 쉽게 해결할 수 있다.

 

코드

from sys import stdin


def dfs(w, h):

    if dp[w][h]:
        return dp[w][h]

    if w == 0:
        return 1

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

    if h > 0:
        dp[w][h] += dfs(w, h - 1)

    return dp[w][h]


if __name__ == '__main__':
    dp = [[0] * 31 for _ in range(31)]

    while True:
        n = int(stdin.readline())

        if n == 0:
            break

        print(dfs(n, 0))