[BOJ][python] 11444. 피보나치 수 6

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

11444번: 피보나치 수 6

---

💡IDEA

수학과 분할 정복을 사용하는 문제이다.

피보나치 수열을 계산할 때 동적 계획법이나 변수 두개를 치환하면서 갱신하는 식으로 풀었었는데, 이 문제는 n이 너무 커서 감당할 수가 없다.

어떻게 풀어야할지 도무지 모르겠어서 https://www.acmicpc.net/blog/view/28 의 도움을 받았다.

n이 굉장히 클 때 피보나치 수열을 계산하기 위해서는 행렬 제곱을 사용해야 한다.

행렬로 피보나치 수열 계산하기

아래 코드에서 matmul 함수는 행렬 곱셈 후 1000000007로 나누어주는 연산을 해주고, solve 함수는 초기 행렬 a를 b제곱하는 연산을 수행한다. 제곱하는 수인 b가 홀수인 경우에는 $a^{b-1}×a$ 로 계산하고, 짝수인 경우에는 $(a×a)^{b/2}$ 로 계산한다.

 

📌CODE

N = int(input())
mod = 1000000007

def matmul(a, b):
    M = len(b[0])
    mul = [[0]*M for _ in range(2)]
    for r in range(2):
        for c in range(M):
            tmp = 0
            for i in range(2):
                tmp += a[r][i] * b[i][c]
            mul[r][c] = tmp%mod
    return mul

def solve(a, b):
    if b == 1:
        return a
    if b%2:
        return matmul(solve(a, b-1), a)
    else:
        return solve(matmul(a, a), b//2)

if N<=2:
    print(1)
else:
    print(matmul(solve([[1, 1], [1, 0]], N-2), [[1], [1]])[0][0])