백준 11444번: 피보나치 수 6 [python]

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

문제 접근

dp로 풀었던 피보나치 문제는 행렬의 거듭제곱으로도 계산이 가능하다.

피보나치 수열은 다음 점화식을 따른다.

F(n) = F(n-1) + F(n-2)

이걸 행렬로 표현하면 다음과 같은 관계가 성립한다.

[ F(n+1) F(n)   ]   =   [1 1]^n
[ F(n)   F(n-1) ]       [1 0]

즉, 아래의 기본 행렬을 n-1제곱 한 뒤 [0][0] 원소를 출력하면 F(n) 값을 얻을 수 있다.

A^(n-1) = [[F(n), F(n-1)],
           [F(n-1), F(n-2)]]

행렬 A = [[1, 1], [1, 0]] 를 n-1번 거듭제곱한 결과의
왼쪽 위 원소가 바로 우리가 구하고 싶은 F(n) 이다.

해답 및 풀이

```python
import sys
input = sys.stdin.readline 

MOD = 1000000007  # 문제에서 요구하는 나머지 연산의 기준값

# 두 2x2 행렬 A, B를 곱하는 함수
def mat_mul(A, B):
    return [
        [
            (A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD,  # 왼쪽 위 원소
            (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD   # 오른쪽 위 원소
        ],
        [
            (A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD,  # 왼쪽 아래 원소
            (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD   # 오른쪽 아래 원소
        ]
    ]

# 반복문을 이용한 행렬 거듭제곱 함수 (분할 정복 기반)
def mat_pow(matrix, n):
    result = [[1, 0], [0, 1]]  # 단위 행렬로 초기화 (곱셈 항등원)
    while n > 0:
        if n % 2 == 1:  # n이 홀수면 result에 한 번 곱해줌
            result = mat_mul(result, matrix)
        matrix = mat_mul(matrix, matrix)  # 행렬 제곱
        n //= 2  # n을 절반으로 줄여가며 반복
    return result  # n제곱한 결과 행렬 반환

# 입력 받기
n = int(input())

# 예외 처리: F(0)은 0
if n == 0:
    print(0)
else:
    base = [[1, 1], [1, 0]]  # 피보나치 기본 행렬
    result = mat_pow(base, n - 1)  # base^(n-1)을 계산하면 F(n)이 나옴
    print(result[0][0])  # 결과 행렬의 [0][0] = F(n)