[DP/동적계획법] 백준 13699 점화식 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

13699번: 점화식

 

 

 

2. 문제 풀이

t(0) = 1
t(n) = t(0)*t(n-1) + t(1)*t(n-2) + ... + t(n-1)*t(0)

 위와 같은 점화식이 주어집니다. 점화식에 따라 t(n)을 구해야 합니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 이전에 계산했던 값을 반복해서 사용하는 구조입니다. 따라서 메모이제이션 해두고, 다음 항을 구할 때 사용합니다.

 

 

 

3. 코드

# 입력
n = int(input())

# DP
cache = [1, 1, 2]
for i in range(3, n+1):
    tmp = 0
    for j in range(i):
        tmp += cache[j] * cache[i-j-1]
    cache.append(tmp)
print(cache[n])

 파이썬의 리스트는 '가변'길이를 가지고 있으므로, 굳이 n까지 초기화할 필요는 없습니다. 점차 늘려나가셔도 괜찮습니다.