BOJ 11444: 피보나치 수 6

✔ 문제 링크

BOJ 11444: 피보나치 수 6

---

✔ 문제해결전략

• Recursion

---

✔ 해결과정

n이 최대 1e+18이다. 이 크기의 long long 타입 배열을 잡으려면 256mb로는 어림도 없다. 따라서 메모이제이션을 통한 DP로 해결이 불가능하다. 이 문제에서는 피보나치 수를 행렬로 표현하고 행렬 곱셈을 이용하여 n 번째 피보나치 수를 구해야 한다. 피보나치 수를 행렬로 표현하면 아래와 같다.

위 그림 아래 행렬식에서 우항의 행렬은 {{F2, F1}, {F1, F0}}이다. 이 행렬을 n 제곱하면 된다. BOJ 1629: 곱셈, BOJ 10830: 행렬 제곱에서 본 것처럼 어떤 수 및 행렬의 n 제곱은 log(n)에 구할 수 있다. 그 방법을 그대로 적용하면 된다.

---

✔ 정답 CODE

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

vvll baseMatrix = {{1,1}, 
                {1,0}};

vvll multiplyMatrix(const vvll& m1, const vvll& m2, int n) {
    vvll result(n, vector<ll>(n));
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            for(int k=0;k<2;k++) {
                result[i][j] += m1[i][k] * m2[k][j];
                result[i][j] %= MOD;
            }
        }
    }
    return result;
}

vvll fibo(ll k) {
    if(k==1) return baseMatrix;
    vvll ans = fibo(k/2);
    ans = multiplyMatrix(ans, ans, 2);
    // exp == odd
    if(k&1) return multiplyMatrix(baseMatrix, ans, 2);
    // exp == even
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n;
    cin >> n;

    vvll fiboMatrix = fibo(n);
    cout << fiboMatrix[1][0];

}

---

✔ Comment

BOJ 1629: 곱셈, BOJ 10830: 행렬 제곱는 이걸 풀기위한 빌드업. 흐름이 마음에 든다. 아이패드도 값어치를 하는 것 같아서 마음에 든다.

---

✔ More

피보나치 수를 구하는 여러가지 방법