백준 11444, 피보나치 수 6

문제

https://www.acmicpc.net/problem/11444

풀이

이 문제는 못풀어서 풀이 방법을 봤다... 따라서 상세 풀이 설명을 생략하겠다.

처음에는 n 탐색으로는 절대 안될 것 같아서 로그 탐색으로 할 수 있나 생각해 봤지만 쉽게는 안풀릴 것 같아 혹시 수학 관련 문제인가 싶어

이런 식을 푸는 과정을 통해 같을 꼴로 나타내어 제곱 분할 정복을 만들려 했지만 실패했다.

그래도 1시간 정도 생각하다가 포기 하고 정답을 봤는데... 행렬 곱셈을 통한 풀이 였다.

선형대수를 제대로 공부하지 않아서 발생한 문제라 생각된다... 복습해야겠다.

실수

• 구현 과정에서 ret = ret와 같이 값을 바로 사용하려다가 로직을 제대로 파악하지 못하여 값이 꼬이는 상황이 발생, 결국 temp를 만들어 해결 (시간 낭비)
• 행렬 곱셈을 한지 오래되어 구현하는데 시간이 오래걸림

코드

#define _CRT_SECURE_NO_WARNINGS

#include<vector>
#include<iostream>

using namespace std;

vector<vector<long long int>> ret_mat = { {1, 1}, {1, 0} }; // 재귀에서 반환할 행렬
vector<long long int> init = { 1, 1 };
vector<vector<long long int>> u = { {1, 1}, {1, 0} };

void DC(long long int n) {

	if (n == 1) {

		ret_mat[0][0] = u[0][0];
		ret_mat[1][0] = u[1][0];
		ret_mat[0][1] = u[0][1];
		ret_mat[1][1] = u[1][1];

		return;

	}

	else {

		if (n % 2 == 1) {

			DC((n - 1) / 2);

			vector<vector<long long int>> temp = { {0, 0}, {0, 0} };

			temp[0][0] = ret_mat[0][0];
			temp[1][0] = ret_mat[1][0];
			temp[0][1] = ret_mat[0][1];
			temp[1][1] = ret_mat[1][1];

			ret_mat[0][0] = temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0];
			ret_mat[0][1] = temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1];
			ret_mat[1][0] = temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0];
			ret_mat[1][1] = temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1];

			temp[0][0] = ret_mat[0][0];
			temp[1][0] = ret_mat[1][0];
			temp[0][1] = ret_mat[0][1];
			temp[1][1] = ret_mat[1][1];

			ret_mat[0][0] = temp[0][0] * u[0][0] + temp[0][1] * u[1][0];
			ret_mat[0][1] = temp[0][0] * u[0][1] + temp[0][1] * u[1][1];
			ret_mat[1][0] = temp[1][0] * u[0][0] + temp[1][1] * u[1][0];
			ret_mat[1][1] = temp[1][0] * u[0][1] + temp[1][1] * u[1][1];

			ret_mat[0][0] = ret_mat[0][0] % 1000000007;
			ret_mat[0][1] = ret_mat[0][1] % 1000000007;
			ret_mat[1][0] = ret_mat[1][0] % 1000000007;
			ret_mat[1][1] = ret_mat[1][1] % 1000000007;
		

		}

		else {

			DC(n / 2);

			vector<vector<long long int>> temp = { {0, 0}, {0, 0} };

			temp[0][0] = ret_mat[0][0];
			temp[1][0] = ret_mat[1][0];
			temp[0][1] = ret_mat[0][1];
			temp[1][1] = ret_mat[1][1];

			ret_mat[0][0] = temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0];
			ret_mat[0][1] = temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1];
			ret_mat[1][0] = temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0];
			ret_mat[1][1] = temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1];

			ret_mat[0][0] = ret_mat[0][0] % 1000000007;
			ret_mat[0][1] = ret_mat[0][1] % 1000000007;
			ret_mat[1][0] = ret_mat[1][0] % 1000000007;
			ret_mat[1][1] = ret_mat[1][1] % 1000000007;

		}

		return;

	}

}

int main() {

	long long int n;

	scanf("%lld", &n);

	DC(n);

	printf("%lld", ret_mat[1][0]);

	return 0;

}