[백준/2749/파이썬] 피보나치 수3

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

2749번: 피보나치 수 3

Problem

• 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
• 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

조건

• n=17일때 까지 피보나치 수를 써보면 다음과 같다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
• n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
• 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

SOL

피보나치 수열을 푸는 방법은 정말 많다.

1. 재귀적으로 구현하기 2. 반복문 이용하기 , 3. DP 이용하기 , 4. 일반항 이용하기 등등.

하지만, 이번에 공부한 방법은 행렬의 곱셈을 이용해서, 피보나치 수열을 나타내는 방법이였다.

이렇게 피보나치 수열을 나타내면, O(logN)이라는 O(N)보다 훨 -씬 빠른 알고리즘이 완성이 된다.

설명이 엄청 길고, 행렬에 대한 지식이 있어야 하기 때문에, 따로 글을 작성할거고, 이 글에서는 제가 읽은 블로그 글의 링크를 첨부해놓겠습니다!

 

import sys
input= sys.stdin.readline
#피보나치
#행렬의 곱셈으로 피보나치 나타내기

# fibo: An+2 = An+1+An
# in Matrix, [An+2]  = [1 1]  * [An+1] 
#            [An+1]    [1 0]     [An]
# 수열로 나타내면,[An+2]  = [1 1] ^ n+1 *[a1]
#                [An+1]    [1 0]        [a0]

def Fibo(n):
    SIZE=2
    identity_element=[[1,0],[0,1]]
    BASE=[[1,1],[1,0]]
    def cal_mul(a,b,size=SIZE):
        new=[[0 for _ in range(size)] for _ in range(size)]
        
        for i in range(size):
            for j in range(size):
                for k in range(size):
                    new[i][j] = (new[i][j]+a[i][k] *b[k][j])%1000000
        return new
    #Base 행렬을 N번 곱한 행렬을 만들어주는 곳
    def get_nth(n):
        matrix=identity_element.copy()
        k=0
        tmp=BASE.copy()
        
        while 2 ** k<=n:
            #print("k:{},matrix:{},tmp:{}".format(k,matrix,tmp))
            if n & (1 << k) !=0:
                matrix=cal_mul(matrix,tmp)
            k+=1
            tmp = cal_mul(tmp,tmp)

        return matrix
    return get_nth(n)[1][0]
N=int(input())
print(Fibo(N))

https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95.html

피보나치 수열 알고리즘을 해결하는 5가지 방법