[백준] 피보나치 수 6 (11444번) - Python

✅문제 - 피보나치 수 6 (11444번)

---

 

✅필요 알고리즘 개념 - 분할 합

---

🔵 자연수 a의 1024제곱을 구하는 상황 

◼ Dynamic Programming이나 재귀를 이용하면 최소 1024번의 연산을 진행해야 한다.

◼ (a^2)^2 = a^4 인 성질을 이용하면 a^1024 를 10번의 계산으로 구할 수 있다.

    이는 제곱 연산의 분할 합 개념을 이용한 것이다.

 

🔵 피보나치 수열의 분할 합 개념

피보나치 수열을 행렬을 통하여 구할 수 있다.

이 개념을 적용하면 피보나치 수열을 다음과 같이 표현할 수 있다.

이 때 행렬의 n제곱을 하는 과정에서 위에 말한 분할 합의 개념을 적용하면 행렬의 n제곱을 쉽게 구할 수있다.

이를 통해 피보나치 수열의 n항을 쉽게 구할 수 있다.

 

✅코드

---

import sys

input = sys.stdin.readline
prime_num = 1000000007
mat = [[1,1],[1,0]]

# 2*2 행렬의 곱을 구하는 함수
def mul_matrix(a:list,b:list):
    changed = list(zip(*b))
    result = [[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            tmp = 0
            for k in range(2):
                tmp += a[i][k]*changed[j][k]
            result[i][j] = tmp%prime_num
    return result

# 2*2 행렬의 제곱을 구하는 함수
def suquare_matrix(a:list):
    changed = list(zip(*a))
    result = [[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            tmp = 0
            for k in range(2):
                tmp += a[i][k]*changed[j][k]
            result[i][j] = tmp%prime_num
    return result

# 행렬의 n제곱을 구하는 함수 / 분할합 개념과 재귀를 이용해 구성
def involution_matrix(n:int):
    if n == 1:
        return mat
    else:
        if n % 2:
            return mul_matrix(suquare_matrix(involution_matrix((n-1)//2)),mat)
        else:
            return suquare_matrix(involution_matrix(n//2))

n = int(input().rstrip())
if n <= 2:
    print("1")
else:
    # 피보나치의 1항과 2항이 1인 것을 이용해 합을 구한다.
    print(sum(involution_matrix(n-2)[0])%prime_num)