[2748] 피보나치 2

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

import sys

n = int(sys.stdin.readline().strip())
fibos = [0 for _ in range(n+1)]

def fibo(n):
    if n==0:
        return 0
    if n==1:
        return 1
    return fibos[n-2] + fibos[n-1]

for nn in range(n+1):
    fibos[nn] = fibo(nn)

print(fibos[-1])

 

피보나치 수 n은 피보나치 수 n-2와 피보나치 수 n-1의 수의 합으로 이루어져있다

 

피보나치 수 0부터 n까지 계산하면 메모이제이션을 통해 중복계산을 피할 수 있다

 

점화식

 

fibo[n] = fibo[n-2] + fibo[n-1]