[14495] 피보나치 비스무리한 수열 (Python)

[문제]

https://www.acmicpc.net/problem/14495

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

---

알고리즘 분류는 다이나믹 프로그래밍 입니다.

1, 1, 1, 2, 3, 4, 6, 9, ... 이 곳에서 점화식을 찾아서 풀어야 합니다.

---

[코드]

import sys

fibo = [1, 1, 1]
for i in range(117):
    fibo.append(fibo[i] + fibo[i + 2])

n = int(sys.stdin.readline())
print(fibo[n - 1])

점화식은 f[i] + f[i + 2] 입니다.