[백준 11444번] 피보나치 수 6 (Python3)

문제의 압도적인 n의 제한범위 (n은 1,000,000,000,000,000,000보다 작거나 같은 자연수)를 보자마자 분할정복 거듭제곱으로 푸는거구나 를 깨닫긴 했는데, 어떻게 풀어야 할지 막막했다.

 

그렇게 끄적끄적 고민하다가 놀라운 사실을 발견했는데, 바로 피보나치 수가 피보나치 수를 피보나치 수의 곱으로 나타낼 수 있다는 것이었다.

 

발견하게된 이유는 3은 1+2인데, 5는 2+3이다. 그런데 5는 2+(1+2)이므로 1이 1번 2가 2번 쓰인다.

8은 5+3이므로 2+3+3이고, 이는 2+(1+2)+(1+2) 이다. 2가 3번, 1이 2번 쓰인다.

 

규칙이 보이지 않는가? 작은 숫자들의 개수도 똑같이 피보나치 수열인 것이다.

 

 

이 규칙을 이용해 조금 만지다 보면 이런 식을 발견할 수 있다.

n이 홀수일 때, fibo(n) = fibo(n//2)**2 + fibo(n//2+1)**2

 

n이 짝수인 경우는 피보나치의 기본성질인 fibo(n+1)-fibo(n-1)로 구해주면 된다.

 

코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())

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)%1000000007
    else:
      memory[n] = (Fibo(n+1)-Fibo(n-1))%1000000007
    return memory[n]

print(Fibo(n))

memory dictionary를 이용한 방법은 행렬의 거듭제곱을 할때 생각해낸 방법인데, 그때는 굳이 필요하지 않았지만, 이번 문제에서는 아주 유용하게 쓰였다.

다른 사람들 풀이를 보니 행렬의 거듭제곱을 이용한 사람들이 많아보였다. 선형대수학을 공부해야하는건가....

어쨌든 난 내 나름대로의 방식으로 풀었으니 만족이다.

 

 

오늘의 교훈) 행렬에 대해서 공부해보자