분할 정복을 이용한 문제이다. 우선 입력으로 주어지는 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;
}