[파이썬] 10870 피보나치 수 5

처음에 재귀함수로 풀이

 

하지만 재귀함수로 하면 겹치는 계산이 존재해서 다른 풀이도 찾아보았다.

 

import sys

def fibo(n):
  if n == 0:
    return 0
  elif n <= 2:
    return 1
  return fibo(n-1) + fibo(n-2)
n = int(sys.stdin.readline())
print(fibo(n))

 

 

---

 

다른 풀이

https://leejunggae.tistory.com/9

 

이미 계산한 값은 배열에 저장했다가 꺼내서 쓰는 방법.

import sys

n = int(sys.stdin.readline())

lst = [0] * (n+1) #피보나치 0~n
def fibo(n):
  if lst[n] != 0:
    return lst[n]
  elif n < 2:
    lst[n] = n
    return lst[n]
  else:
    lst[n] = fibo(n-1) + fibo(n-2)
    return lst[n]
    
print(fibo(n))