[boj] 백준 11444 피보나치 수 6 python 풀이

문제

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

11444번: 피보나치 수 6

 

문제 풀이

피보나치 수열을 구하는 방법 중에 수열을 이용한 방법을 구현함. 메모제이션을 사용하는 법도 기억해두자,,

참고 ref ) https://www.acmicpc.net/blog/view/28

피보나치 수를 구하는 여러가지 방법

 

코드

import sys
input = sys.stdin.readline

def matrix_power(adj,n):
    if n==1:
        return adj
    elif n%2:
        return matrix_multiply(matrix_power(adj,n-1),adj)
    else:
        return matrix_power(matrix_multiply(adj,adj),n//2)

def matrix_multiply(matrix1, matrix2):
    leng = len(matrix1)

    result = [[0] * leng for _ in range(leng)]
    
    for i in range(leng):
        for j in range(leng):
            for k in range(leng):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000000007
    
    return result

power = int(input().strip())

result = matrix_power([[1, 1], [1, 0]], power)
print(result[-1][0])