백준(Python) 2747번 피보나치 수 풀이

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

 

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

2747번: 피보나치 수

---

data = [0] * 46

def fibo(x) :
  if x == 0 :
    return 0
  if x == 1 or x == 2 :
    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이거나 2라면 1을 반환한다. 둘 다 아닐 경우 data 리스트의 해당 인덱스 값이 0이 아니라면 그 값을 반환한다.

 

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