[백준 2086번] 피보나치 수의 합 (Python3)

import sys
input = sys.stdin.readline

memory = {1:1,2:1,3:2,4:3,5:5}

def Fibo(n):
  if memory.get(n):
    return memory[n]
  else:
    if n%2 == 1:
      memory[n] = (Fibo(n//2)**2+Fibo(n//2+1)**2)%1000000000
    else:
      memory[n] = (Fibo(n+1)-Fibo(n-1))%1000000000
    return memory[n]

a,b = map(int,input().split())
print((Fibo(b+2)-Fibo(a+1))%1000000000)

일단 풀이는 매우 쉽다. 피보나치 수열의 합을 쭉 나열해보면 0 1 2 4 7 12 20 33 54 88 ... 이 나오는데, 이를 피보나치 수열인 0 1 1 2 3 5 8 13 21 34 와 비교해보면 피보나치 수열의 n까지의 합은 n-2번째 피보나치 수에서 1을 빼준 수와 같다는 규칙성이 보이게 된다.

 

따라서 [백준 11444번] 피보나치 수 6 (Python3) (tistory.com) 의 코드를 그대로 이용해서 풀 수 있었다.

 

다만 어떻게 증명하느냐가 문제인데, 이는 시그마 공식을 이용하면 유도할 수 있다.

Sn = an+an-1+...+a0

Sn-1 = an-1+an-2+...+a0

Sn-2 = an-2+an-3+...+a0

이를 정리해보면 Sn, Sn-1, Sn-2 사이에 Sn = Sn-1+ Sn-2 + 1이라는 규칙이 성립한다는 것을 알 수 있다.

 

피보나치 수의 성질에 대해서 알려주는 좋은 문제였다.

 

오늘의 교훈) 피보나치 수는 재미있다.