(c++) BOJ 11444번: 피보나치 수 6

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

11444번: 피보나치 수 6

 

---

 

 

문제 개요

 

 

백준 10830번: 행렬 제곱 문제를 응용해서 푸는 문제이다.

코드 자체도 비슷하고, 분할 정복 방법도 똑같은 문제이기에 한 번 볼 필요가 있다.

 

먼저 피보나치와 행렬 간에 어떤 유사점이 있는지 살펴보면

 

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

 

이러한 관계를 가지고 있다.

n 행렬의 제곱이 n+1 행렬이 되는 것을 볼 수 있다.

 

$$ \begin{pmatrix}
0 & 1 \\
1 & 1 \\
\end{pmatrix} ^{1} \times \begin{pmatrix}
0 & 1 \\
1 & 1 \\
\end{pmatrix} ^{1} = \begin{pmatrix}
1 & 1 \\
1 & 2 \\
\end{pmatrix} ^{2} $$

 

n이 홀수일 경우에도 앞선 문제와 같이

 

n-1 행렬과 n=1 행렬을 곱해주면 된다.

 

 

코드

 

입력값 n이 큰 값이기에 long long으로 선언하고, 벡터 또한 long long으로 선언한 모습을 볼 수 있다.

값이 많이 크기에 곱셈 부분에서 행렬의 값을 따로 1,000,000,007의 나머지로 계산했다.

#include <bits/stdc++.h>

using namespace std;

long long n;
// matrix = 피보나치 n=1, temp = 제곱한 피보나치 행렬
vector matrix(2, vector<long long>(2, 0));
vector<vector<long long> > temp;

//행렬의 곱셈
vector<vector<long long> > matrix_mult(vector<vector<long long> >m_1, vector<vector<long long> > m_2) {
    vector result(2, vector<long long>(2, 0));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                result[i][j] += (m_1[i][k] % 1000000007) * (m_2[k][j] % 1000000007);
            }
        }
    }
    return result;
}

// 거듭제곱 재귀이용
vector<vector<long long> > pow(long long m) {
    if (m == 1) return matrix;
    //홀수일 때
    if (m % 2 > 0) return matrix_mult(pow(m-1), matrix);
    vector<vector<long long>> pow_m = pow(m / 2);
    return matrix_mult(pow_m, pow_m);
}


int main(void) {
    cin >> n;
    matrix[0][0] = 0, matrix[0][1] = 1,
    matrix[1][0] = 1, matrix[1][1] = 1;
    temp = pow(n);
    cout << temp[0][1] % 1000000007;
}