[BOJ 11444] 피보나치 수 6

피보나치 수 6 (Gold 3)

문제

전체 문제 보기

11444번: 피보나치 수 6

접근법

피보나치 수는 아래의 점화식을 따릅니다.

 

\[f(n) = f(n-1) + f(n-2) \]

 

그런데 이번 문제에서 n의 크기는 매우 큽니다. 그래서 Brute Force로는 해결할 수 없고 행렬의 제곱으로 문제를 해결해야 합니다. 위 점화식을 행렬로 표현하면 아래와 같이 나타낼 수 있습니다.

 

\[\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} = \begin{pmatrix} f(n-1) + f(n-2) \\ f(n-1) \end{pmatrix} = \begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix}\]

 

만약 \(n\)번째 피보나치 수를 계산해야 한다면 \(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 행렬을 \(n\) 곱해서 \(n\)번째 피보나치 수를 구할 수 있습니다.

\[\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix}\]

그래서 이번 문제를 풀기 위해서는 행렬의 제곱 연산을 최적화할 필요가 있습니다. 행렬의 제곱은 \(O(n)\)에서 \(O(\mbox{log}n)\)으로 최적화할 수 있습니다. 최적화 방법은 이 문제에서 확인할 수 있습니다.

성능 평가

이번 문제는 행렬의 제곱을 최적화하여 n번째 피보나치 수를 구하는 문제로 시간 복잡도는 행렬의 제곱 연산에 좌우됩니다. 행렬의 제곱 연산의 시간 복잡도는 \(O(\mbox{log}n)\) 입니다.

전체 소스 코드

#include <iostream>
#include <array>
#define endl '\n'
using namespace std;
const long long MOD = 1'000'000'007;
using Matrix = array<array<long long, 2>, 2>;

Matrix operator* (const Matrix& lhs, const Matrix& rhs)
{
    Matrix ret{};
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            for (int k = 0; k < 2; ++k)
            {
                ret[i][j] += (lhs[i][k] * rhs[k][j]) % MOD;
                ret[i][j] %= MOD;
            }
        }
    }
    return ret;
}
Matrix Pow(const Matrix& mat, long long fac)
{
    if (fac == 1)
        return mat;

    Matrix ret;
    if (fac % 2 == 0) // 짝수
    {
        ret = Pow(mat, fac / 2);
        ret = ret * ret;
    }
    else // 홀수
    {
        ret = Pow(mat, fac - 1) * mat;
    }
    return ret;
}

int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    long long n; // 1,000,000,000,000,000,000보다 작거나 같은 자연수
    cin >> n;
    Matrix mat;
    mat[0] = { 1, 1 };
    mat[1] = { 1, 0 };

    mat = Pow(mat, n);
    cout << mat[0][1] << endl;

    return 0;
}