[백준 7677] Fibonacci (python)

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

7677번: Fibonacci

Fibonacci 문제

-1을 받을 때까지 반복하고, 숫자의 마지막 4자리를 출력하는 문제

분할정복을 이용하여 해결할 수 있었다.

📌문제 접근 포인트

1. 먼저 피보나치수열을 구해보자. N의 크기가 매우 큰 숫자이기에 재귀 or DP로는 절대로 시간 안에 들어오기 어려운 구조다.
2. 그렇다면 분할 정복을 이용해서 필요한 경우만 빠르게 찾아낼 수 있도록 구성해 보자. 피보나치수열의 경우 행렬로 나타내면 [[1,1], [1,0]]의 형태의 반복된 곱으로 구할 수 있는 구조로 되어 있다. 이 행렬의 n제곱을 활용한 분할정복을 해보자.
3. 2개의 행렬을 곱해주는 행렬의 곱 함수를 만들어주고, n제곱을 구해줄 함수를 만들어 행렬을 n제곱해주었고, 이때의 행렬의 [1][0] 인덱스에 해당하는 것으로 N번째 피보나치수열을 구해줄 수 있다. 
4. n번째 피보나치 수의 마지막 4자리를 출력해 주기 위해서 %10000을 계산해서 출력하면 어렵지 않게 해결할 수 있었다.

⚙️ 내가 푼 정답 코드

def mult(a,b): # 행렬의 곱을 구하자
    A = [[0,0],[0,0]] # 2차원 행렬
    for i in range(2): 
        for j in range(2):
            for k in range(2):
                A[i][j] += a[i][k] * b[k][j] % 10000 # a, b 행렬의 곱 이고 중간에 10000으로 나눠도 결과는 동일
    return A  # 나누지 않고 반환하면 값이 너무 커서 처리시간 증가 

def f(x, n): #행렬을 n번 곱했을 때의 피보나치 수열 구하기
    if n == 1: 
        return x 
    else : 
        matrix = f(x,n//2) # 행렬이 n이 1이 될 때까지 재귀 반복 
        if n % 2 == 0: # 짝수면
            return mult(matrix, matrix) # 행렬끼리 곱해주기
        else: # 홀수면
            return mult(mult(matrix,matrix), x) # 행렬 곱한거에 한번 더 곱해주기

import sys
while True:
    N = int(sys.stdin.readline())
    if N == -1:
        break
    elif N == 0:
        print(0)
    else:
        x = [[1,1],[1,0]]
        result = f(x,N)
        print(result[0][1] % 10000) # n번 째 피보나치 수