알고리즘/백준 문제풀이

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

감자156 2023. 7. 21. 14:21
반응형

문제

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

 

11444번: 피보나치 수 6

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

문제 풀이

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

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

 

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

피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ 피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같습니다. 피보나치 수를 구하는 함수

www.acmicpc.net

 

코드

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])

 

반응형