(C++) - 백준(BOJ) 11444번 : 피보나치 수 6

 

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

11444번: 피보나치 수 6

행렬 곱셈을 이용해 log n만에 피보나치를 구하는 문제였습니다.

 

풀이방법

​F(n) = F(n-1) + F(n-2) (n > 2) 를 행렬로 나타내면 다음과 같습니다.

 

{\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix}} = {\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}} X {\begin{pmatrix} F(n-1) \\ F(n-2) \end{pmatrix}}

 

 

1. 행렬로 피보나치 수열을 연산하게 되면 log(n)으로 시간복잡도를 낮출 수 있습니다.

 

2. n & 1 == 1 즉 n이 홀수라면 (a X ans) ^ 2를

짝수라면 a ^ 2를 해주어 최적화 할 수 있습니다.

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

Code

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll = long long;
using mat = vector<vector<ll>>;
ll n;

mat mulMatrix(mat &a, mat & b){
    mat 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(){
    cin >> n;
    mat ans = {{{0,1},{1,0}}};
    mat a = {{1,1},{1,0}};
    while(n > 0){
        if(n & 1) ans = mulMatrix(a,ans);
        a = mulMatrix(a,a);
        n /= 2;
    }   
    cout << ans[0][0];
}