[백준 11444번] 피보나치 수 6 (C++)

문제링크 : https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>>matrix;
const int MAX = 987654321;
const int MOD = 1000000007;


matrix multiply (matrix&a, matrix&b)
{
    matrix tmp(2, vector<ll>(2));
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            for(int k=0; k<2; k++)
            {
                tmp[i][j] += a[i][k] * b[k][j];
            }
            tmp[i][j]%=MOD;
        }
    }
    return tmp;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    ll N;
    cin >> N;
    matrix result = {{1, 0}, {0, 1}}; //초기값(단위행렬)
    matrix x = {{1, 1}, {1, 0}};

    while(N)
    {
        if(N%2) result = multiply(result, x); //홀수
        x = multiply(x, x); //짝수
        N/=2;
    }
    cout << result[0][1];
    return 0;
}

N이 굉장히 크기에 피보나치수가 행렬 제곱으로 표현될 수 있다는 것을 안다면 나름 수월하게 풀리고, 모른다면 힘든 문제이다.

 

나도 이번 문제를 풀면서 처음 알게되었다.

 

기본적으로 피보나치를 행렬로 표현하면 다음과 같다.

[Fn+2] = [1 1] [Fn+1]
               [ Fn ]

 

추가적으로 다음과 같은 식을 도출할 수 있다.

[Fn+1] = [1 0] [Fn+1]
               [ Fn ]

 

위 2개를 이용하면 또 다음과 같은 식을 도출할 수 있다.

[Fn+2] = [1 1] [Fn+1]
[Fn+1] = [1 0] [ Fn ]

 

각 값을 result+1 = x * result 이렇게 치환해서 계산해보면 규칙이 보인다.

reuslt1 = x * result0
result2 = x * result1 = x * (x * result0) = x^2 * result0
result3 = x * result2 = x * (x * result1) = x * (x * (x * result0)) = x^3 result0

resultn = x^n * result0

 

다시 이를 행렬식으로 표현해보자

[Fn+1] = [1 1]^n [1]
[ Fn ] = [1 0]   [0]

 

행렬 제곱은 다음과 같이 계산이 가능하다.

result8 = result4 * result4
        = (result2 * result2) * (result2 * result2)
        = ((result1 * result1) * (result1 * result1)) * ((result1 * result1) * (result1 * result1))

result5 = result4 * result1
        = (result2 * result2) * result1
        = ((result1 * result1) * (result1 * result1)) * result1

위와 같이 짝수 일때는 나누기2를 해서 분할해주고, 홀수 일때는 똑같이 나누기 2를 해주고 남은 것을 한번 곱해준다.

아래 예시를 보자

N = 9라고 가정

9 -> 홀수 -> I * A1 : result(A1)
             A1 * A1 : A2
             
4 -> 짝수 -> A2 * A2 : A4

2 -> 짝수 -> A4 * A4 : A8

1 -> 홀수 -> result(A1) * A8 = A9

 

이렇듯 홀 수 일때는 따로 한 번더 곱해주고 이외에는 계속 곱하면서 값을 저장해나간다.