백준 2748번 피보나치수 2 : 다이나믹 프로그래밍

import sys
# 다이나믹 프로그래밍: 시간 초과를 막기 위한 메모제이션
fires=[0,1,1]
def fire(n):
    if n ==0:
        return 0
    elif n==1:
        return 1
    elif len(fires)>n: # 이미 값을 계산한 적이 있다면 그 값을 바로 리턴
        return fires[n]
    else:
        save= fire(n-1)+fire(n-2)
        fires.append(save)
        return save
N = int(input())
print(fire(N))