백준(Python) 풀이/수학

백준(Python) 10870번 피보나치 수 5

개발윗미 2021. 10. 6. 12:21

Python으로 구현한 10870번 피보나치 수 5 문제 풀이입니다.

 

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

 

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net


data = [0] * 21

def fibo(x) :
  if x == 0 :
    return 0
  if x == 1 :
    return 1
  if data[x] != 0 :
    return data[x]
  data[x] = fibo(x - 1) + fibo(x - 2)
  return data[x]

n = int(input())
print(fibo(n))

 

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 

 

그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

 

그렇기 때문에 피보나치 수를 구하는 메서드 fibo( ) 내에서 전달받은 값이 0이라면 0을 반환하고 1이라면 1을 반환한다.

 

둘 다 아닐 경우 data 리스트의 해당 인덱스 값이 0이 아니라면 그 값을 반환한다.

 

만약 해당 인덱스 값이 0이라면 바로 앞 두 피보나치 수의 합으로 갱신하여 반환한다.