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

11444번: 피보나치 수 6

분할 정복을 이용한 문제이다. 우선 입력으로 주어지는 n의 최댓값이 굉장히 크기때문에 일반적인 방법으로 구하면 시간 초과가 발생한다. 행열의 제곱을 이용하여 문제를 해결했다. 피보나치 수를 행렬로 나타내면 아래와 같다.

$\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1&1 \\ 1&0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix}$ 

위의 행렬을 정리하게되면 아래의 행렬 식이 된다.

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

n만큼 제곱을 한 후, 1,000,000,007로 나눈 나머지를 출력해주었다.
어려웠던 문제였다. 피보나치 수를 구하는 새로운 방법을 알게되었다.

---

#include <iostream>

using namespace std;

long long n;

void multi(long long m1[][2], long long m2[][2]) {
    long long tmp[2][2];

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            long long temp = 0;

            for (int k = 0; k < 2; k++) {
                temp += (m1[i][k] * m2[k][j]);
            }
            tmp[i][j] = temp % 1000000007;
        }
    }

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            m1[i][j] = tmp[i][j];
        }
    }
}

void solution(){
    long long m[2][2] = { 1,1,1,0 };
    long long res[2][2] = { 1,0,0,1 };

    while (n > 0) {
        if (n % 2 == 1) {
            multi(res, m);
        }

        n /= 2;
        multi(m, m);
    }

    cout << res[1][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    long long m[2][2] = { 1,1,1,0 };
    long long res[2][2] = { 1,0,0,1 };

    while (n > 0) {
        if (n % 2 == 1) {
            multi(res, m);
        }

        n /= 2;
        multi(m, m);
    }

    cout << res[1][0];

    return 0;
}