BOJ 11444 피보나치 수 6

문제

접근 방법

기존 피보나치 문제와 동일하지만 구하는 n이 1,000,000,000,000,000,000보다 작거나 같은 자연수라는 점에서 색다른 문제였다. $O(n)$으로도 이 문제는 해결하지 못하므로 $O(logn)$ 풀이를 생각해냈어야 했다. 피보나치 수는 일반적으로 아는 F(n) = F(n-1) + F(n-2) 말고도 다른 규칙이 존재한다.

\[F_{2n−1}​=F_n^2​+F_{n−1}^2​​\] \[F_{2n}​=(F_{n−1}​+F_{n+1})F_n​=(2F_{n−1}​+F_n​)F_n​\]

이 규칙을 사용하면 logN으로 풀이를 생각해낼 수 있다. 이때, 연산을 반복하지 않기 위해서 이미 계산한 피보나치 값을 저장해뒀다가 즉시 반환활 수 있게 만들었다.

정답 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e9))

n = int(input())
memo = dict()
memo[0] = 0
memo[1] = 1
memo[2] = 1
def fibo(k):
  if k in memo:
    return memo[k]

  elif k % 2 == 0:
    m = k//2
    f_1 = fibo(m)%1000000007
    f_2 = fibo(m+1)%1000000007
    f = (f_1 * (2 * f_2 - f_1)) %1000000007
    memo[k] = f
    return f

  else:
    m = k // 2
    f_1 = fibo(m)%1000000007
    f_2 = fibo(m+1)%1000000007
    f = (pow(f_1,2)%1000000007 + pow(f_2,2)%1000000007)%1000000007
    return f

print(fibo(n))

  

느낀 점

비정상적인 input 값을 보면 divide conquer 를 생각해야겠다.