BOJ 2748 피보나치 수 2

문제

접근 방법

일반적인 재귀 방법으로 피보나치를 계산하면 시간 초과가 난다.

import sys
input = sys.stdin.readline

def fibo(k):
  if k==0:
    return 0
  elif k==1 or k==2:
    return 1

  return fibo(k-1) + fibo(k-2)


n = int(input())

print(fibo(n))

피보나치가 호출될 때 마다 다른 피보나치 함수가 2번 호출되어 최대 $2^90$ 만큼 호출이 될 수 있게 된다.

더 간단하게 풀기 위해서 DP를 떠올렸다. 이전 피보나치 값들을 가지고 있다면 n번째 피보나치 수가 바로 계산될 수 있기 때문이다.

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
fibos = [-1]*(91)

fibos[0], fibos[1], fibos[2] = 0, 1, 1

for i in range(3,n+1):
  fibos[i] = fibos[i-1] + fibos[i-2]

print(fibos[n])