지극히 개인적인 공부 노트/알고리즘(Algorithm)

[Algorithm] 백준 11444번: 피보나치 수 6 | 분할 정복법, 행렬 제곱, 나머지 연산 규칙

AS J 2021. 9. 2. 10:29
문제 출처: https://www.acmicpc.net/problem/11444


1. 결과

메모리 29200KB, 시간 88ms

2. 풀이

이 문제는 평범한 재귀 호출이나 동적 계획법과 같은 연산을 통해 구하기가 쉽지 않다. 문제 조건에서 볼 수 있듯이 Fn을 구하는데, 해당 n이 최대 10^17(10의 17제곱)까지 가능하기 때문이다. 또한 피보나치 수열은 궁극적으로 앞의 연속된 두 숫자를 알아야만 그 다음 숫자를 구할 수 있고, 앞의 연속된 두 숫자는 또 해당 숫자의 앞의 연속된 두 숫자를 알아야만 연산이 가능하다. 즉, 기존의 피보나치 수열 개념( Fn = Fn-1 + Fn-2 (n ≥ 2) )은 연쇄적으로 연산이 되기 때문에, 각각의 독립된 소문제 해결을 통해 큰 문제를 해결하는 일반적인 분할 정복 방식도 적용하기가 쉽지 않다.

해결 방법을 고민하던 중, 피보나치 수열을 초기값(F0 = 0, F1 = 1)과 행렬( [[1, 1], [1, 0]] )의 곱 또는 2 이상의 제곱을 통해 해결할 수 있다는 것을 알 수 있었다. 그리고 더 나아가 [[Fn+1, Fn], [Fn, Fn-1]]은 [[1, 1], [1, 0]]의 곱 또는 제곱만으로 연산이 가능했다. 이는 재귀 호출로만 가능한 줄 알았던 문제를 분할 정복법을 이용한 행렬의 제곱 연산 문제로 변환할 수 있는 포인트였다.

분할 정복법을 이용한 행렬의 큰 수 제곱 연산은 이전에도 구해본 적이 있었기 때문에 어렵지 않게 구현할 수 있었으며, 1,000,000,007로 나눈 나머지를 결과로 가져와야 한다는 점까지 잊지 않고 연산에 포함했다. 여기서도 곱셈에서의 나머지 연산 규칙( (A*B) % P = ((A%P) * (B%P)) % P )이 적용될 수 있기 때문에, 각각의 행렬 연산에도 나머지 연산을 적용시키며 어떤 과정에서든 숫자가 너무 커지지 않도록 방지했다.

그리고 피보나치 수를 구하는 문제가 이 문제의 제목만 봐도 최소 6가지의 경우가 존재한다는 것을 알 수 있다. 나중에는 한 번 이런 시리즈 문제 풀이 방법을 모아서 정리해보는 것도 재밌을 것 같다.

import sys

# 행렬의 곱으로 피보나치 수열 연산 가능
# [[Fn+1, Fn], [Fn, Fn-1]] = [[1, 1], [1, 0]] ^ n
def dotAB(a, b):
    result = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] += a[i][k] * b[k][j]
            result[i][j] %= 1000000007
    return result

def getFibonacci(arr, n):
    if n == 1: return arr
    fibo = getFibonacci(arr, n//2)
    if n % 2: return dotAB(arr, dotAB(fibo, fibo))
    else: return dotAB(fibo, fibo)

def main():
    n = int(sys.stdin.readline())
    fibo_arr = [[1, 1], [1, 0]]
    Fn = getFibonacci(fibo_arr, n)[0][1]
    return Fn % 1000000007

if __name__ == "__main__":
    print(main())