[BOJ, Python] 11444번_피보나치수 6

백준 11444번

문제 난이도: 골드 2
혼자의 힘으로 풀었는가?: X

해당 문제를 처음 본 순간 떠오른 풀이 방식은 단순 피보나치 수열을 구현해서 푸는 방식이었다.
당연하게도 n<=1000000000000000000 이기 때문에 시간 복잡도에서 막힌다.

dp로 풀어야하는지.. 어떻게 풀어야할지 한참을 고민하다가 스스로 정해둔 제한 시간 30분을 넘겼기 때문에 알고리즘 분류를 참고했다.

알고리즘 분류를 확인해보니 분할 정복이라고 한다.

분할 정복이란?

분할 정복이 무엇인지는 이해했는데 이걸 어떻게 피보나치 수열에 적용할지가 고민이었다.

이에 대한 GPT의 대답은 아래와 같다.

상상도 못했던 풀이 방법이었다. 행렬식을 사용할 생각을 왜 못했을까..
선형대수학의 중요성과 생각의 폭의 중요성을 깨달았다.

이제 점화식도 알았으니 코드로 구현해보자.

import sys
input = sys.stdin.readline

def matrix_mult(A, B): # 행렬식의 곱셉
    return [
        [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
        [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]
    ]

def matrix_power(matrix, n): # 분할 정복
    if n == 1:
        return matrix
    elif n % 2 == 0:
        half_power = matrix_power(matrix, n // 2)
        return matrix_mult(half_power, half_power)
    else:
        return matrix_mult(matrix, matrix_power(matrix, n - 1))

def fibonacci(n): # 피보나치 수열
    if n == 0:
        return 0
    elif n == 1:
        return 1
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = matrix_power(base_matrix, n - 1)
    return result_matrix[0][0]

N = int(input())
print(fibonacci(N)*1000000007) # 문제의 요구사항에 따라 1000000007으로 나눈 나머지 출력

풀이는 총 3가지 함수로 나뉜다.

• 행렬식의 곱셈: matrix_mult
• 분할 정복: matrix_power
• 피보나치 수열: fibonacci

1. matrix_mult
   matrix_mult 함수는 두 2x2 행렬식 A, B의 곱을 계산하는 함수이다.
   A = [[a0, a1], [a2, a3]]
   B = [[b0, b1], [b2, b3]]
   행렬 A,B가 위와 같다면 두 행렬식의 곱셉 C는
   C = [[a0*b0+a1*b2, a0*b1+a1*b3], [a2*b0+a3*b2, a2*b1+a3*b3]]

따라서 이를 코드로 표현하면

def matrix_mult(A, B): # 행렬식의 곱셉
    return [
        [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
        [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]
    ]

이와 같다.

2. matrix_power
   matrix_power은 분할 정복을 구현한 함수이다.
   
   단순히 이것을 코드로 구현할 뿐이다.

def matrix_power(matrix, n):
    if n == 1:
        return matrix
    elif n % 2 == 0:
        half_power = matrix_power(matrix, n // 2)
        return matrix_mult(half_power, half_power)
    else:
        return matrix_mult(matrix, matrix_power(matrix, n - 1))

3. fibonacci
   fibonacci 함수는 익숙히 하는 형태와 비슷하다. 단순히 base_matrix를 만들어서 matrix_power 함수로 넘겨주고 그 반환값의 [0][0] 위치에 있는 값을 반환하면 된다.

def fibonacci(n): # 피보나치 수열
    if n == 0:
        return 0
    elif n == 1:
        return 1
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = matrix_power(base_matrix, n - 1)
    return result_matrix[0][0]

그런데 문제가 하나 생겼다.
모든 테스트 출력과 반례에서는 통과했는데 한가지를 간과한 것이다.

여기서 한 가지 의문점이 있었다.
분할 정복 알고리즘은 시간 복잡도가 O(logn)이다. 때문에 매우 큰 n에 대해서도 빠르게 계산이 가능한데 왜 시간 초과가 발생한 것일까?

이유는 매우 큰 값에 있었다. n이 커질수록 중간 결과의 값이 매우 커진다. 이런 경우 많은 메모리를 차지하고, 잠재적인 오버플로우 문제가 생길 수 있다.

해결 방법은 간단하다.
모든 행렬 곱셈 연산 후에 결과를 MOD(1000000007)로 나누도록 하여, 중간 결과가 너무 커지지 않도록 보장하면 된다.

최종 코드

import sys
input = sys.stdin.readline

MOD = 1000000007

def matrix_mult(a, b, mod=MOD):
    return [
        [(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod, (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod],
        [(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod, (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod]
    ]

def matrix_power(mat, n, mod=MOD):
    if n == 1:
        return mat
    elif n % 2 == 0:
        half_mat = matrix_power(mat, n // 2, mod)
        return matrix_mult(half_mat, half_mat, mod)
    else:
        return matrix_mult(mat, matrix_power(mat, n - 1, mod), mod)

def fibonacci(n, mod=MOD):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        base_matrix = [[1, 1], [1, 0]]
        return matrix_power(base_matrix, n - 1, mod)[0][0]

N = int(input())
print(fibonacci(N) % MOD)

이 처럼 행렬 곱셈 연산 단계에 나눗셈을 추가해주면 중간 결과가 일정 크기 이상 커지지 않기 때문에 메모리 문제와 오버플로우 문제를 해결할 수 있다.

결과