[BOJ] 11444 피보나치 수 6

문제 링크

 

www.acmicpc.net/problem/11444

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제는 일반적인 재귀함수로 풀면 시간 초과를 받고, 메모이제이션을 적용하려 해도 메모리 제한에 걸리게 된다.

이 문제는 피보나치 수를 행렬로 생각하고, 행렬의 거듭제곱을 이용해서 풀어야 한다.

 

현재 피보나치 수와 이전 수를 각각 1행, 2행에 배치한 2X1 행렬을 생각해보자. 이 다음 피보나치 수를 구하려면 두 수를 더한 수를 첫 번째 행에, 기존에 첫 번째 행에 있던 현재 피보나치 수는 두 번째 행으로 옮겨줘야 한다. 이런 동작은 아래와 같은 행렬 곱셉으로 간단하게 수행할 수 있다.

 

현재 피보나치 수가 1, 이전 피보나치 수가 1이라고 했을 때, 행렬 [[1 1], [1 0]]을 곱해주면 다음 피보나치 수 2를 얻을 수 있다. 이 행렬을 두 번 곱하면 그 다음 피보나치 수를 구할 수 있고, 이와 같은 과정이 반복된다.

행렬 [[1 1], [1 0]]을 한 번 곱했을 때 2X1 행렬의 두 번째 행의 수가 첫 번째 피보나치 수이고, 두 번 곱하면 두 번째 피보나치 수가 된다. 따라서 행렬 [[1 1], [1 0]]을 n번 곱했을 때 2X1 행렬의 두 번째 행의 수가 n번째 피보나치 수가 되고, 이는 행렬 [[1 1], [1 0]]을 n제곱한 행렬의 2행 1열의 수와 같다. 따라서 분할정복을 이용해 행렬 [[1 1], [1 0]]의 n제곱을 구해주고, 여기서 2행 1열의 값이 문제의 답이 된다. 오버플로우가 발생하지 않게 행렬의 수를 long long으로 선언해주고, 행렬 곱을 수행할 때마다 1,000,000,007로 나눈 나머지를 저장하자.

 

행렬 곱을 수행하는 함수는 아래와 같다.

 

Matrix matrixMul(Matrix a, Matrix b) {
	Matrix ret(2);
	int i, j, k;
	for (i = 0; i < 2; i++) {
		ret[i].resize(2);
		for (j = 0; j < 2; j++) {
			ret[i][j] = 0;
			for (k = 0; k < 2; k++) {
				ret[i][j] += a[i][k] * b[k][j];
				ret[i][j] %= MOD;
			}
		}
	}
	return ret;
}

 

Matrix는 vector<vector<long long>> 형이며, 3중 for문을 이용해서 행렬 곱을 구한 뒤 결과를 리턴해주는 식으로 작성했다. 이 함수를 행렬 n제곱을 구하는 함수에 사용한다. n이 1이라면 [[1 1], [1 0]]을 리턴해주고, 홀수라면 func(n-1)과 [[1 1], [1 0]]을 곱한 행렬을 리턴하고, 짝수라면 func(n/2)의 리턴 값 두 개를 곱한 행렬을 리턴해준다.

 

Matrix func(long long n) {
	if (n == 1) return init;
	Matrix tmp;
	if (n % 2) { // n 홀수
		tmp = func(n - 1);
		return matrixMul(init, tmp);
	}
	else { // n 짝수
		tmp = func(n / 2);
		return matrixMul(tmp, tmp);
	}
}

 

주의할 점은, matrixMul() 함수 안에서 func() 함수를 재귀호출하면 안된다. 이렇게 할 경우 한번 구했던 행렬을 여러 번 구하게 되어 시간초과를 받게 된다. 변수 tmp를 선언해서 여기에 재귀함수의 리턴값을 저장하도록 하자.

 

전체 코드는 아래와 같다.

 

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<long long>> Matrix;
const int MOD = 1e9 + 7;
long long n;
Matrix init = { {1, 1}, {1, 0} };

Matrix matrixMul(Matrix a, Matrix b) {
	Matrix ret(2);
	int i, j, k;
	for (i = 0; i < 2; i++) {
		ret[i].resize(2);
		for (j = 0; j < 2; j++) {
			ret[i][j] = 0;
			for (k = 0; k < 2; k++) {
				ret[i][j] += a[i][k] * b[k][j];
				ret[i][j] %= MOD;
			}
		}
	}
	return ret;
}

Matrix func(long long n) {
	if (n == 1) return init;
	Matrix tmp;
	if (n % 2) { // n 홀수
		tmp = func(n - 1);
		return matrixMul(init, tmp);
	}
	else { // n 짝수
		tmp = func(n / 2);
		return matrixMul(tmp, tmp);
	}
}

int main(){
	cin >> n;
	if (n == 0) {
		cout << 0;
		return 0;
	}

	Matrix ret = func(n);
	cout << ret[1][0];
}