[Python] 백준11444 피보나치 수 6

03 Jul 2023 in Study on Algorithm

백준11444 피보나치 수 6 링크

문제

예제 입력

---

코드

X = 1000000007
N = int(input())
arr = [[1,1],[1,0]]

def matrix_mul(mat1, mat2):
    tmp = [[0]*2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                tmp[i][j] += mat1[i][k] * mat2[k][j] % X

    return tmp

def sol(n):
    if n == 1:
        return arr
    else:
        tmp = sol(n//2)
        if n % 2 == 0:
            # ([1, 1][1, 0])n/2 * ([1, 1][1, 0])n/2
            return matrix_mul(tmp, tmp)
        else :
            # ([1, 1][1, 0])n-1/2 * ([1, 1][1, 0])n-1/2 * ([1, 1][1, 0])
            return matrix_mul(matrix_mul(tmp, tmp), arr)

ans = sol(N)
print(ans[0][1] % X)
# print(ans[1][0] % X)

# 피보나치 수를 빠르게 풀 수 있는 방법은 다음과 같습니다

# 1.재귀 => O(2^n)
# 2.dp (메모제이션) => O(N)
# 3.피사노 주기(피보나치 수를 K로 나눈 나머지는 항상 주기를 가짐)
# 4.행렬 => O(log N)

# ([Fn+2][Fn+1]) = ([1, 1][1, 0]) * ([Fn+1][Fn])
# ([Fn+1, Fn][Fn, Fn-1]) = ([1, 1][1, 0])n
# ([Fn+1][Fn]) = ([1, 1][1, 0])n * ([F1][F0])
# 짝수 ([1, 1][1, 0])n = ([1, 1][1, 0])n/2 * ([1, 1][1, 0])n/2
# 홀수 ([1, 1][1, 0])n = ([1, 1][1, 0])n-1/2 * ([1, 1][1, 0])n-1/2 * ([1, 1][1, 0])

# 도가뉴 항등식
# x^n = x^a * X^b
# n = a + b
# n = 2a(a = b)
# ([Fn+1, Fn][Fn, Fn-1]) = ([1, 1][1, 0])n
# Fn-1 = Fa * Fb + Fa-1 * Fb-1
# F2a-1 = Fa^2 + Fa-1^2
# Fn = Fa+1 * Fb + Fa * Fb-1
# F2a = Fa * (Fa + 2Fa-1)

설명

파이썬을 통해서 사용자로부터 입력받아 분할 정복 알고리즘으로 사용하여 피보나치 수 6를 구현했습니다.

---

결과