백준11444 (피보나치 수6)[C/C++]

🔗링크

1. 문제 풀이

이 문제는 행렬곱과 분할정복을 통해 풀이하였다.
우선 입력이 굉장히 큰값으로 주어짐으로 일반적인 피보나치 수를 구하는 공식을 사용할 시 시간초과가 나오게 된다.
그렇기에 분할로 풀이하기 위한 점화식을 유도한다.
이전에 풀어본 분할을 통한 거듭제곱, 행렬제곱의 풀이를 떠올리며 이를 응용하기 위해 행렬식으로 유도해보면

$\begin{bmatrix}f_{n+1}\\f_n\end{bmatrix} = \begin{bmatrix}f_n + f_{n -1}\\f_n + 0\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix}$

$\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}f_{n - 1}\\f_{n-2}\end{bmatrix}$

$\begin{bmatrix}f_{n+1}\\f_{n}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}f_{n - 1}\\f_{n-2}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^2\begin{bmatrix}f_{n - 1}\\f_{n-2}\end{bmatrix}$

$\begin{bmatrix}f_{n+1}\\f_{n}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n\begin{bmatrix}f_1\\f_0\end{bmatrix}$

이러한 식을 도출할 수 있다.
이 식과 백준10830번(행렬 제곱)의 알고리즘을 이용하면 문제가 해결된다.
+모듈러 연산 잊지않기

2. 코드

#include<stdio.h>
#define m 1000000007
typedef long long ll;

ll M[2][2] = { 1,1,1 };
ll I[2][2] = { 1,1,1 };

void Pow(ll n) {
	ll T[2][2] = {0};
	if (n % 2) {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int k = 0; k < 2; k++)T[i][j] = (T[i][j] + (M[i][k] * I[k][j]) % m) % m;
	}
	else
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int k = 0; k < 2; k++)T[i][j] = (T[i][j] + (M[i][k] * M[k][j]) % m) % m;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)M[i][j] = T[i][j];
}

void f(ll n) {
	if (n < 2)return;
	else if (n % 2)f(n - 1);
	else f(n / 2);
	Pow(n);
}

int main() {
	ll input;
	scanf("%lld", &input);
  f(input);
	printf("%lld",M[1][0]);
	return 0;
}

3. 후기

힌트 안봤으면 못풀었을것 같다
수학 좀 더 공부하자,,,