[Python] BOJ 4811번. 알약

작성일 | In |

4811번. 알약

문제 링크

풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 4811번. 알약


import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)


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]


dp = [[0 for i in range(31)] for i in range(31)]

while True:
    n = int(input())

    if n == 0:
        break
    print(dfs(n, 0))  # 처음에는 완전한 n개의 알약이 있음

비고