[BOJ] 11444번: 피보나치 수 6

 

11444번: 피보나치 수 6

사용 알고리즘

• divide and conquer
• memoization

시간 복잡도

• O($M^3 log N$) :  ( M : 행렬의 크기, N : N번째 항 )

---

풀이

N이 아주 큰 $10^18$이기 때문에, 일반적인 1차원의 DP 점화식을 이용해서는 풀 수 없다.

점화식을 행렬의 형태로 표현하였으며, 행렬의 거듭제곱을 이용하여 시간복잡도가 O($M^3 log N$)로 풀 수 있다.

 

피보나치의 일반적인 점화식은 A[n] = A[n-1] + A[n-2] (A > 2)의 형태이다.

일반적인 점화식의 경우 O($N$)이며, 시간복잡도가 아주 커서 시간 초과가 걸리게 된다.

점화식을 행렬의 형태로 표현한 후 거듭제곱을 이용한 식의 예시는 다음과 같다.

 

$A^1$ x $A^1$ = $A^2$

행렬이 $A^N$일 때 1행은 $A^N - 2$, 2행은 $A^N - 1$, 3행은 $A^N$이다. 

 

$A^N$은 = 짝수 일 경우 $A^{N/2}$를 메모이제이션을 이용하여 구한 뒤 제곱을 한 $(A^{N/2})^2$으로 구할 수 있다.

              홀수 일 경우 짝수처럼 $(A^{N/2})^2$에서 $A^1$을 더해준 $(A^{N/2})^2 + A^1$으로구할 수 있다.

---

소스코드

#include<stdio.h>
#define M 1000000007

typedef struct {
	long long m[3][3] = { {0,1,0},
			      {0,0,1},
			      {0,1,1} };
}Z;
Z multi, matrix;

void M_mul(Z a, Z b) {
	for (int y = 0; y < 3; y++) {
		for (int x = 0; x < 3; x++) {
			multi.m[y][x] = a.m[y][0] * b.m[0][x];
			for (int i = 1; i < 3; i++) {
				multi.m[y][x] += a.m[y][i] * b.m[i][x];
			}
			multi.m[y][x] %= M;
		}
	}
}

void Fibo(long long n) {
	if (n > 1) {
		Fibo(n / 2);
		M_mul(multi, multi);
		if (n % 2)
			M_mul(multi, matrix);
	}
}

int main()
{
	int f[3] = { 0,1,1 };
	long long n, ans = 0;

	scanf("%lld", &n);
	if (n > 0) {
		Fibo(n);
		for (int i = 0; i < 3; i++)
			ans += multi.m[0][i] * f[i];
	}
	printf("%lld", ans % M);

	return 0;
}