[백준] 피보나치 수 6

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

11444번: 피보나치 수 6

행렬의 거듭제곱을 분할정복으로 구해서 해결하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, n번째 피보나치 수를 1,000,000,007로 나눈 나머지를 출력해야 하는 문제입니다. 이 때, n은 1,000,000,000,000,000,000보다 작은 숫자라는 조건이 있습니다.

 

<Solution>

처음 시도하였던 방법과, 그 방법이 안되는 이유에 대해 설명하고 문제의 정답에 대해 이야기해 보려 합니다. 

 

이전 까지 문제를 해결할 때, 피보나치 수는 항상 다이나믹 프로그래밍으로 해결하였습니다. 하지만 여기에서 n의 범위가 너무 크기 때문에 다이나믹 프로그래밍으로는 해결할 수 없고, 다른 방법을 생각해야 하는 것을 알 수 있습니다. 

 

그래서 처음 생각한 방법은 피보나치 수의 일반항 공식을 이용하는 것입니다. 결국 안되는 것을 알게 되었지만 생각을 정리해보려 합니다. 

 

방법 1. 피보나치 수의 일반항

흔히 n번째 피보나치수열은 위와 같은 일반항이 잘 알려져 있습니다. (유도과정은 인터넷에 많이 있으니 궁금하신 분들은 참고하시면 될 것 같습니다) 

 

하지만 피보나치 수열의 일반항에는 root(5)가 존재하고, 무리수입니다. 컴퓨터에서 floating point의 표현방법으로 저장하게 되는데, 이 때 필연적으로 오차가 존재합니다. 따라서 만약 위의 일반항에서 n제곱을 그대로 구하면 오차가 누적되어 실제 값과 다른 결과를 얻을 것입니다. 

실제로 다음과 같이 오차가 발생하는 것을 쉽게 확인 할 수 있습니다. 

 

(ps. 그렇다면 실수 두개가 같은지는 어떻게 비교해야 하는가? )

https://dojang.io/mod/page/view.php?id=2466 

파이썬 코딩 도장: 47.7 실수 값의 오차

 

자 다시 본론으로 돌아가면, 최종적으로 위의 일반항에서는 자연수가 나오는데 이는 root(5)와 -root(5)가 만나서 모두 상쇄되기 떄문입니다. 이 생각으로 위의 식을 풀어내면 결국 root(5)가 없는 부분이 나오지 않을까? 생각하고 풀어보았습니다.

 

다음과 같이 n번째 피보나치 항을 유도할 수 있습니다. 위의 식에는 root(5)가 존재 하지 않는 것을 알 수 있습니다. 

그래서 이 식을 이용해 해결 할 수 있는지를 생각해보면, 

결국 위의 식을 계산해야 하고, 생각해보면, 1~n!을 구하는 과정이 여러번 반복되므로 dp를 이용해야 하는 것을 생각할 수 있습니다. 하지만 n이 너무 큰 숫자이기에 dp table을 유지하는 것 자체로 메모리 초과가 될 것을 예상할 수 있습니다. 

 

그래서 다른 방법을 생각해야 합니다. 

 

방법2. 행렬을 이용한 피보나치 수열의 계산

위와 같은 과정을 통해 피보나치 수열을 행렬을 이용하여 구할 수 있습니다. [[1,1],[1,0]]의 거듭제곱을 활용하면 i번째 피보나치 수열을 구할 수 있는 것을 알 수 있습니다. (F1 = 1, F0 = 0) 따라서 행렬의 거듭제곱을 분할정복 하는 과정을 통해 특정 번째 피보나치 수열을 빠르게 구할 수 있는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다. 

import sys
sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline().rstrip())

def multiple_matrix(A,B):
    # find dimension (row -> m, column -> n)
    m_A = len(A)
    n_A = len(A[0])
    m_B = len(B)
    n_B = len(B[0])
    assert(n_A == m_B)
    # return matrix
    return_matrix = [[] for _ in range(m_A)]
    tmp = list(zip(*B))

    for i in range(m_A):
        for j in range(n_B):
            return_matrix[i].append(sum(map(lambda x : x[0] * x[1], zip(A[i], tmp[j])))% (int(1e9)+7))
    return return_matrix

def exp(base, expo):
    if expo == 0:
        return [[1,0],[0,1]]
    if expo == 1:
        return base
    a = exp(base, expo//2)
    b = expo%2
    
    if b == 0: 
        return multiple_matrix(a,a)
    else: # b ==1
        return multiple_matrix(multiple_matrix(a,a),base)

# [Fn,Fn-1]^T
tmp = multiple_matrix(exp([[1,1],[1,0]], n-1),[[1],[0]])

print(*tmp[0])