(백준/C++) 11444_피보나치6

11444번: 피보나치 수 6 (acmicpc.net) 문제도 분할 정복(Divide and Conquer)으로 풀어볼 수 있습니다.

분할 정복이란, 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 합쳐 원래 문제의 해결책을 찾는 방법입니다.

이 문제는 행렬의 곱셈과 관련있기 때문에, 다음의 문제들을 풀어보고 푸는 것을 추천 드립니다.

1629번: 곱셈

10830번: 행렬 제곱

---

접근법

피보나치의 행렬 접근 아이디어는 다음과 같습니다.

\[\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}F_n\\F_{n-1}\end{pmatrix}=\begin{pmatrix}F_n+F_{n-1}\\F_n\end{pmatrix}\]

이 행렬을 $n$번 곱하면 $F_{n+1}$과 $F_n$을 얻을 수 있습니다. $(F_{n+1}=F_n+F_{n-1})$

이 식을 다르게 풀어보면 다음과 같습니다.

\[\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}F_1\\F_0\end{pmatrix}=\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}\]

이러한 접근법을 가지고 분할 정복(Divide and Conquer)의 세가지 접근법으로 나누어 생각해보겠습니다.

1) 분할(Divide)

이 문제는 $A^n$을 분할 정복으로 계산할 수 있습니다. 이를 더 작은 문제로 나눌 때, $n$이 짝수일 경우와 홀수일 경우로 나누어 생각할 수 있습니다.

• $n$이 짝수일 때: $A^n=(A^{n/2})^2$
• $n$이 홀수일 때: $A^n=A×(A^{n-1/2})^2$

2) 정복(Conquer)

분할한 문제를 재귀적으로 해결합니다. $A^{n/2}$ 나 $A^{(n-1)/2}$ 을 재귀적으로 호출해 나아갑니다.

기저 사례(Base Case): $n=1$ 일 때, 더 이상 분할할 필요가 없으므로 결합 단계로 넘어갑니다.

3) 결합(Combine)

분할한 문제의 해를 결합하여 원래 문제의 해를 구합니다.

여기에서는 분할 정복한 문제($A^{n/2}$ 나 $A^{(n-1)/2}$)를 제곱해서 계산하기 시작합니다.

즉, $n$이 짝수일 때 $A^n=(A^{n/2})^2$, $n$이 홀수일 때 $A^n=A×(A^{n-1/2})^2$ 로 결합을 합니다.

---

풀이

문제에서 1000000007을 나눈 나머지를 계산하라고 했으니, 이를 염두에 두고 짜야 합니다.

제 경우에는 기본 행렬 A를 직접 결합하는 방식을 사용했습니다.

$n/2$로 계속 나누다가 결합 단계에서 $A^2$으로 계산하고, $n$이 홀수인 경우에 기본 행렬을 곱해주는 방식으로 계산 했습니다.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> InitMatrix = { {1, 1}, {1, 0} };
constexpr int MOD = 1000000007;

void mulMatrix(vector<vector<int>>& A, const vector<vector<int>>& B)
{
	int _a = ((long long)A[0][0] * B[0][0] + (long long)A[0][1] * B[1][0]) % MOD;
	int _b = ((long long)A[0][0] * B[0][1] + (long long)A[0][1] * B[1][1]) % MOD;
	int _c = ((long long)A[1][0] * B[0][0] + (long long)A[1][1] * B[1][0]) % MOD;
	int _d = ((long long)A[1][0] * B[0][1] + (long long)A[1][1] * B[1][1]) % MOD;

	A[0][0] = _a;
	A[0][1] = _b;
	A[1][0] = _c;
	A[1][1] = _d;
}

void makeMatrix(vector<vector<int>>& A, long long n)
{
	if (n <= 1) return;

	makeMatrix(A, n / 2); // 절반으로 계속 나누다가

	mulMatrix(A, A); // (A^(1/2))^2 으로 계산합니다.

	if(n & 1)
	{
		// 만약 n이 홀수였다면, A * (A^(1/2))^2 으로 계산되어야 합니다.
		mulMatrix(A, InitMatrix);
	}
}

long long fibonacci(long long n)
{
	// 행렬 | 1 1 |   |F(n-1)|   |F(n-1)+F(n-2)|
	//      | 1 0 | x |F(n-2)| = |F(n-1)       |
	if (n == 0) return 0;
	else if (n == 1) return 1;

	vector<vector<int>> result = InitMatrix;
	makeMatrix(result, n - 1);

	return result[0][0];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	long long N;
	cin >> N;

	cout << fibonacci(N);
}