[BOJ] 11444번 : 피보나치 수6 (도가뉴 항등식)

접근

피보나치 수를 구하는 문제이다.

하지만 범위가 괴랄한.. $ n <=  1,000,000,000,000,000,007 $

기본적인 개선법인 메모이제이션으론 해결이 불가능하다고 생각.

구글에 피보나치 수를 검색해보았다.

 

위키백과에 피보나치 수의 성질을 봤더니 "도가뉴 항등식"이라는 성질을 만족시킨다는 것을 발견https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98#%ED%95%AD%EB%93%B1%EC%8B%9D

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

문제 분류도 분할정복을 이용한 거듭제곱의 계산이 들어있다.

그럼 짝수, 홀수항을 나눠서 구하는 형태의 문제로 예상이 된다.

 

해결

도가뉴 항등식은 간단한 변형으로 짝수항과 홀수항을 나눠서 구할 수 있다.

짝수항 $ 2n $

기본 도가뉴 항등식에 $ m = n $을 대입하면,

$$
F_{2n} = F_{n-1}F_n + F_nF_{n+1} \\ F_{2n} = F_n(F_{n-1} + F_{n+1}) \\
= F_n(F_{n-1} + (F_n + F_{n-1})) \\
= F_n(F_n + 2F_{n-1})
$$

홀수항 $ 2n+1 $

기본 도가뉴 항등식에 $ m = n+1 $을 대입하면,

$$
F_{n+1+n} = F_nF_n + F_{n+1}F_{n+1} \\
F_{2n+1} = F_n^2 + F_{n+1}^2
$$

 

이렇게 짝수항과 홀수항의 점화식을 각각 도출해낼 수 있다.

이 것들을 이용해서, 피보나치 수를 구하는 함수를 구현하면, 아래와 같다.

 

코드

from collections import defaultdict

n = int(input())
dp = defaultdict(int)

dp[0] = 0
dp[1] = 1
dp[2] = 1

def fibonacci(n):
    if not dp[n]:
        if n & 1: # 홀수면
            fn = fibonacci(n//2)
            fn_p1 = fibonacci(n//2 + 1)
            
            dp[n] = (fn ** 2 + fn_p1 ** 2) % 1_000_000_007
        else: # 짝수면
            fn = fibonacci(n//2)
            fn_m1 = fibonacci(n//2 - 1)
            
            dp[n] = (fn * (fn + 2 * fn_m1)) % 1_000_000_007
        
    return dp[n]

print(fibonacci(n))