문제 (BOJ 11444)
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
입출력
입력 : 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
출력 : 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.
//입력
1000
//출력
517691607
C++
복사
풀이
기존의 DP를 이용한 피보나치는 O(N)에 해결 가능했다. 하지만 주어진 수의 범위가 엄청나게 크므로 O(N) 시간에는 문제를 해결할 수 없다. 따라서 피보나치의 이론 중 하나인 행렬의 곱을 이용한 피보나치 계산법과 분할정복을 이용한 거듭제곱의 문제 해결법을 사용하여 O(log N)에 문제를 해결해야 한다.
행렬곱을 사용한 피보나치 표현
따라서 F(N)을 구하기 위해서는 [1,1][1,0] 행렬의 n제곱을 한 후 2행 1열에 있는 수를 구하면 된다.
이 때 행렬의 N제곱을 전부 수행하면 O(N)이 되므로 분할정복을 사용한다.
(
지수식의 O(lgN)알고리즘은, 분할정복의 일종으로
예를들어 A의 10승을 계산한다고 하면, A의 5승의 제곱이고, A의 5승은 A의 2승 * A의 3승... 이렇게 이분할로 줄여나갈 수 있다.
)
•
Cal 함수 ( 행렬곱을 수행하는 함수)
Matrix는 vector<vector<long long>> 형이며, 3중 for문을 이용해서 행렬 곱을 구한 뒤 결과를 리턴해주는 식으로 작성했다. 이 함수를 행렬 n제곱을 구하는 함수에 사용한다.
matrix cal(matrix a, matrix b) {
matrix ret(2, vector<long long>(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
ret[i][j] += a[i][k] * b[k][j];
}
ret[i][j] %= mod;
}
}
return ret;
}
C++
복사
•
Solve 함수 ( 분할정복을 수행하는 함수)
n이 1이라면 [[1 1], [1 0]]을 리턴해주고, 홀수라면 func(n-1)과 [[1 1], [1 0]]을 곱한 행렬을 리턴하고, 짝수라면 func(n/2)의 리턴 값 두 개를 곱한 행렬을 리턴해준다.
matrix solve(ll n) { // 1 1 1 0 행렬의 N승을 구하는
matrix temp;
if (n == 1) return origin;
if (n % 2 == 1) { // 홀수
temp = solve(n - 1);
return cal(temp, origin);
}
else { //짝수
temp = solve(n / 2);
return cal(temp, temp);
}
}
C++
복사
주의할 점은, matrixMul() 함수 안에서 func() 함수를 재귀호출하면 안된다. 이렇게 할 경우 한번 구했던 행렬을 여러 번 구하게 되어 시간초과를 받게 된다. 변수 tmp를 선언해서 여기에 재귀함수의 리턴값을 저장하도록 하자.
•
전체 코드
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <string>
#include <algorithm>
#pragma warning(disable:4996)
#define all(x) (x).begin,(x).end
#define INF int(1e9)
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define txtcin freopen("input.txt", "r", stdin);
#define fst first
#define snd second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<vector<ll>> matrix;
ll mod = 1000000;
ll N;
matrix origin = { {1,1},{1,0} };
matrix cal(matrix a, matrix b) {
matrix ret(2, vector<long long>(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
ret[i][j] += a[i][k] * b[k][j];
}
ret[i][j] %= mod;
}
}
return ret;
}
matrix solve(ll n) { // 1 1 1 0 행렬의 N승을 구하는
matrix temp;
if (n == 1) return origin;
if (n % 2 == 1) { // 홀수
temp = solve(n - 1);
return cal(temp, origin);
}
else { //짝수
temp = solve(n / 2);
return cal(temp, temp);
}
}
int main() {
fastio;
cin >> N;
matrix answer = solve(N);
cout << answer[1][0];
return 0;
}
C++
복사
중요
이차원 벡터의 초기화
matrix ret(2, vector<long long>(2)); //[2][2] 크기의 벡터를 0으로 초기화한다.
matrix ret(6, vector<long long>(5,0)); // [6][5] 크기의 벡터를 0으로 초기화한다.
C++
복사
