백준 11444 피보나치 수 6 - 파이썬

문제.

 

풀이.

피보나치를 행렬의 거듭제곱으로 풀 수 있다는 사실을 몰랐었는데 이번 문제를 풀면서 알게되었다.

피보나치를 그냥 계산하면 시간 복잡도가 O(n)을 가지지만 행렬의 거듭제곱을 이용하면 O(logn)의 시간 복잡도를 가지게 된다.

식은 다음과 같다.

 

소스코드.

import sys

def Square(b):
    if b == 1:
        return matrix
    temp = Square(b // 2)
    if b % 2 == 0:
        result = matrix_multiple(temp,temp)
        return result
    elif b % 2 == 1:
        result = matrix_multiple(temp,temp)
        result = matrix_multiple(result, matrix)
        return result

# 행렬 곱
def matrix_multiple(temp1, temp2):
    result_matrix = [[0 for i in range(2)] for j in range(2)]
    for i in range(2):
        for j in range(2):
            result_matrix[i][j] = multiple(i, j, temp1, temp2)
    return result_matrix

# 행렬 곱 연산
def multiple(x, y, temp1, temp2):
    result = 0
    mat2 = [mat[y] for mat in temp2]
    for i, j in zip(temp1[x], mat2):
        result += i * j
    return result % 1000000007

N= int(sys.stdin.readline())

matrix = [[1, 1], [1, 0]]

result = Square(N)
result = result[0][1]
print(result)