[백준 11444 파이썬] 피보나치 수 6 (골드3, 분할 정복)

알고리즘 유형 : 분할 정복
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

n = int(input())
p = 1000000007

# n번 째 피보나치 수는 행렬 (1 1, 1 0)^n 의 1행 2열 값이다(단, n>=1일때)

def mul(A, B):
    n = len(A)
    Z = [[0]*n for _ in range(n)]
    
    for row in range(n):
        for col in range(n):
            e = 0
            for i in range(n):
                e += A[row][i] * B[i][col]
            Z[row][col] = e % p
            
    return Z

def square(A, k):
    if k == 1:
        for x in range(len(A)):
            for y in range(len(A)):
                A[x][y] %= p
        return A
    
    tmp = square(A, k//2)
    if k % 2:
        return mul(mul(tmp, tmp), A)
    else:
        return mul(tmp, tmp)
    
fib_matrix = [[1, 1], [1, 0]]
print(square(fib_matrix, n)[0][1])

풀이 요약

1. 이번 문제는 선형대수 지식이 핵심인 문제였다.

   피보나치 수를 행렬로 나타내보면 다음과 같다고 한다. 실제로 행렬 곱셈을 해보면, 피보나치 점화식을 그대로 나타낸다.

   $\begin{pmatrix}{F}_{n+2}\\{F}_{n+1}\end{pmatrix}\ =\ \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}{F}_{n+1}\\{F}_n\end{pmatrix}$

   
   그리고 이 것을 행렬에 대한 연산, 성질을 이용해서 밑의 식으로 변형할 수 있다고 한다...

   $\begin{pmatrix}{F}_{n+1}&{F}_n\\{F}_n&{F}_{n-1}\end{pmatrix}\ =\ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n$

   
   양 변에 역행렬을 곱해서 (Fn+1, Fn)을 없애주고 거듭제곱을 해주고 등등 하면 될 것 같기도 한데..

   선형 대수 행렬 파트가 가물가물해서 직접 해보긴 어려울 것 같다.. 나중에 제대하고 선형대수 복습한 뒤 직접 유도해봐야겠다.

2. 그 외에는 이제 행렬의 곱셈 함수, 거듭제곱 함수를 작성해서 풀면 끝이다.

   피보나치 수를 DP로 풀면 O(N)의 시간복잡도가 걸리는데, 행렬로 생각해서 풀면 저렇게 행렬의 거듭제곱을 구하는 형태로 바뀌니까, 분할 정복 알고리즘을 사용하여 O(logN)으로 줄어든다.

   행렬의 곱셈 함수, 거듭제곱 함수 로직은 이전에 포스팅한 10380 행렬 제곱 문제 풀이를 참고하자.

배운 점, 어려웠던 점

• 피보나치 수 점화식을 행렬로 나타내고, 이를 식 변형하여 상수 행렬의 거듭제곱 꼴로 나타내는 선형 대수 지식이 필요한 아이디어를 떠올리질 못했다. 나중에 선형대수 행렬 파트 복습하고 직접 유도해봐야겠다...