[DP/동적계획법] 백준 14495 피보나치 비스무리한 수열 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14495번: 피보나치 비스무리한 수열

 

 

 

2. 문제 풀이

f(n) = f(n-1) + f(n-3)

 피보나치 수열 f(n) = f(n-1) + f(n-2)와 달리, f(n-3)이 들어간 수열입니다. 피보나치 수열과 마찬가지로, 점화식만 수정해서 DP로 구현합니다.

 

 

 

3. 코드

# 입력
n = int(input())

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