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

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

11444번: 피보나치 수 6

 

 

# 조건

• 피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

# 접근 방법

• dp를 이용하여 풀었던 이전 문제들과는 다르게 입력값이 어마어마하여
• O(logn)의 알고리즘으로 풀어주어야 한다.
• 행렬과 피보나치 사이에는 아래 그림과 같은 관계가 존재한다.

 

• 즉 위 행렬의 n제곱만 구한다면 피보나치 수를 구할 수 있다.

import sys
input = sys.stdin.readline

n, B = 2, int(input())
A = [[1,1],[1,0]]

def power(a,b,n):
    cal = []
    for i in range(n):
        temp = []
        for j in range(n):
            num = 0
            for k in range(n):
                num += a[i][k] * b[k][j]
            temp.append(num%1000000007)
        cal.append(temp)
    return cal
    # 행렬의 곱셉을 함수화 해보았다.

def dac(s,b):
    if b == 1:
        return s
    
    a = dac(s,b//2)
    
    cal = power(a,a,n)
    
    result = []
    if b % 2:
        result = power(cal,A,n)
    else:
        result = cal
        
    return result
print(dac(A,B)[0][1])