[BOJ][Python]11444 풀이

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

11444번: 피보나치 수 6

def matrix_multiplication(matrix1, matrix2):
    result = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] += matrix1[i][k]*matrix2[k][j]
            result[i][j] %= 1000000007
    return result
            
n = int(input())
ans = [[1, 0], [0, 1]]
fib_mat = [[1, 1], [1, 0]]
while n > 0:
    if n%2 == 1:
        ans = matrix_multiplication(ans, fib_mat)
    fib_mat = matrix_multiplication(fib_mat, fib_mat)
    n //= 2
print(ans[1][0])

정말 좋은 문제인 것 같습니다. 아주 예전에 분할정복을 이용한 제곱 알고리즘의 간단한 문제를 풀었던 적이 있는데, 너무 예전이라 기억도 안났거니와 여기에 적용할 수 있을 거라고 생각을 못했었어요. 알고보면 간단하지만 그 안에 담긴 내용은 전혀 간단하지 않네요. 같이 한 번 알아봅시다.

 

먼저 n번째 피보나치 수를 행렬로 표현하는 방법부터 알아보도록 하겠습니다. 요즘은 정규 교육 과정에 행렬이 포함이 되지 않는단 얘기를 들었습니다. 제가 알기로는 이공계열이 아니더라도 행렬을 사용하는 분야가 많다고 들었는데 고등학생들한테는 오히려 아쉬운 개편이 아닌가 싶습니다. 아무튼 학부 생활을 하면, 특히 공학도가 되신다면 단 하루도 행렬을 보지 않는 날이 없는 학부생활을 보내게 됩니다.

 

뭐, 사설은 넘어가고 아무튼 행렬은 행과 열을 기준으로 수를 나열해둔 것 입니다. 또한 다항식을 행렬의 곱을 이용해서 표현할수도 있습니다. 여기서 사용하는 행렬의 핵심은 이게 되겠네요. 이걸 기준으로 n번째 피보나치 수를 행렬의 곱을 통해서 표현해보겠습니다.

n번째 피보나치 수를 식으로 표현하면 어떻게 되나요?

$$  F_{n} = F_{n-1} + F_{n-2} $$

행렬의 곱셈은 혹시 아직 모르시는 분들을 위해 간단하게 작성을 해보면,

$$ \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} e & f \\ g & h \\ \end{bmatrix}  = \begin{bmatrix} ae + bg & af + bh \\ ce + dg & cf + dh \\ \end{bmatrix}  $$

이 방법에 따라서 n번째 피보나치 수를 행렬의 곱으로 나타내 봅시다.

$$ F_{n} =  \begin{bmatrix} F_{n-1} & F_{n-2} \\ \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix}  $$

위 식이 이해가 되었다면 이제 이렇게도 작성할 수 있겠죠. $ F_{n} $은 평범하게 $ F_{n-1} + F_{n-2} $로 작성을 하면 아래에서 진행할 정리과정이 제대로 진행이 되지 않기 때문에 아래와 같이 $ F_{n} = 1F_{n} + 0F_{n-1} $로 작성합니다. 

$$ \begin{bmatrix} F_{n+1} \\ F_{n} \\ \end{bmatrix} =  \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} F_{n}\\ F_{n-1}\\ \end{bmatrix} $$

이젠 이 식을 좀 더 사용하기 좋게 바꾸기 위한 과정을 좀 진행해보겠습니다. 이미 $ F_{n} = F_{n-1} + F_{n-2} $인건 알았습니다. 그럼 이걸 이렇게도 쓸 수 있을 겁니다. $ F_{n} = F_{n-2} + F_{n-3} + F_{n-3} + F_{n-4} = F_{n-2} + 2F_{n-3} + F_{n-4} $ 이걸 다시 저 위에 있던 식에서 적용시켜보겠습니다. $F_{n}, F_{n-1}$은 이렇게 정리할 수 있죠.

$$ \begin{bmatrix} F_{n} \\ F_{n-1} \\ \end{bmatrix} =  \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} F_{n-1 }\\ F_{n-2}\\ \end{bmatrix} $$

그럼 이제 원래 식에 $ \begin{bmatrix} F_{n} \\ F_{n-1} \\ \end{bmatrix} $를 대입해서 식을 정리하면,

$$ \begin{bmatrix} F_{n+1} \\ F_{n} \\ \end{bmatrix} =  \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{2} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ \end{bmatrix}$$

이렇게 쓸 수 있습니다. 눈치 빠른 분들은 벌써 감이 오셨을겁니다. 이걸 좀 더 정리해보면,

$$ \begin{bmatrix} F_{n+1} \\ F_{n} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n-1} \begin{bmatrix} F_{2}\\ F_{1}\\ \end{bmatrix} $$

이렇게 적을 수 있습니다. 이걸 좀 더 일반화할 수 있을 것 같습니다.

$$ \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n-1} \begin{bmatrix} F_{2} & F_{1}\\ F_{1} & F_{0} \\ \end{bmatrix} $$

$ F_{2}, F_{1}, F_{0} = 1, 1, 0 $ 이니까 다시 작성해보면,

$$ \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n} $$

으로 정리가 가능합니다. 결국 하고 싶었던 말이 뭐냐면 n번째 피보나치 수를 구하기 위해서 [[1, 1], [1, 0]] 을 n 제곱하면 된다는 얘기입니다.

 

이제 이걸 알아냈다면 분할정복을 통한 거듭제곱을 진행해봅시다. 해당 알고리즘의 아이디어는 다음과 같습니다.

$$ (2^{2})^{}2^{1024} = (2^{2})^{512} = (2^{4})^{256} = (2^{8})^{128} = (2^{16})^{64} = (2^{32})^{32} ... $$

당연한 소리를 하고있다 싶을수도 있겠지만 이렇게 생각을 해봅시다.

처음의 $ 2^{1024} $를 구하려면 컴퓨터는 어떻게 계산을 진행할까요. 단순하게 2를 1024번 곱하고 있을 겁니다. 그럼 그 다음은 어떨까요? 처음에 4를 만들기 위해 연산을 1회하고 4를 512번 곱하니까 513회의 연산이 일어나겠네요. 그 다음은요? 8을 만드는데에 2회 그 다음에는 256회니까 259회겠네요. 제가 무슨 말을 하려는지 감이 오시나요? 처음에 제곱수를 만드는 편이 나중에 거듭제곱을 해야하는 연산 횟수를 획기적으로 줄여줍니다. 그래서 이 방법을 이용하면 n번의 제곱 연산을 O(logn)에 끝낼 수 있죠. 물론 거듭제곱을 해야하는 숫자가 점점 커지기 때문에 항상 효율이 좋다고 제가 장담은 못하겠습니다만, 일반적인 상황에서는 죽어라고 몇천번 제곱하고 있는 것 보다 밑을 키우고 지수를 줄이는 쪽이 연산면에서 이득을 볼 수 있겠습니다.

 

그래서 두가지 방법을 다 사용을 해서 해당 문제를 풀게됩니다. 밑이 되는 행렬을 제곱하고 n을 계속 2로 나눠가면서, 홀수가 나왔을 때는 기존에 단위행렬이었던 행렬에 밑이 되는 행렬을 곱해주면서 계산을 해주면 문제의 정답을 시간제한 내에 구할 수 있게됩니다. 홀수일 때는 왜 단위 행렬에 지금의 밑을 곱해주는지 궁금하시면 밑이 행렬이 아니더라도 직접 손으로 써보시면 금방 이해가 되는데요. 말로 설명을 드리자면, 예를 들어 밑이 a이고 현재의 지수가 2n+1이라고 한다면 1에 a를 곱하는 겁니다.  a의 2n+1제곱을 위에서 했던 것처럼 작성하면 $a*(a^{2})^{n}$ 로 쓸 수 있고, 어차피 n을 2로 나눠갈 때 마다 홀수가 되면 그 때의 밑이 하나씩 남게되는 셈인데 나중에 전부 곱할 것이기 때문에 따로 저장을 하지 않고 그냥 미리 남는 걸 하나씩 곱해둔다고 생각하면 됩니다.