[BOJ/백준 2749/C++] 피보나치 수 3

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

2749번: 피보나치 수 3

 

[문제 요약]

- 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

 

- 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

- n=17일때 까지 피보나치 수를 써보면 다음과 같다.

- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

- n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

- 첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

- 시간 제한 : 1초

- 메모리 제한 : 128MB

 

[문제 풀이]

이번 문제는 n이 엄청 매우 큰 경우일때의 피보나치 수를 구해야 한다.

 

우리가 피보나치 수를 구하는 방법 대표적으로 2가지가 있다.

 

첫번째로는 다이나믹 프로그래밍 방법을 이용하여 아래와 같은 식으로 dp[i] = dp[i-1] + dp[i-2] ( i ≥ 2 )를 이용한 방법

 

 

두번째로는 재귀를 이용하여 f(n) = f(n-1) + f(n-2) 구하는 방법이 있다.

 

하지만 재귀의 경우는 dp보다 당연히 효율이 매우 안 좋고, dp방법의 경우도 n이 이번 문제와 같이 매우 큰 경우에선느 적용되지 않는 단점들이 존재한다.

 

따라서 새로운 방법으로 정답을 구해야 하는데 그 방법은 다음과 같다.

따라서 특정 행렬을 n제곱을 하면 우리가 원하는 Fn을 구할 수 있게 된다.

 

그렇다면 행렬을 n제곱을 빠르게 하는 방법을 찾아야 한다.

 

그 방법으로는 다음과 같다.

• N제곱을 한다고 가정했을 때 N을 이진수로 나타낸다.
• 이진수로 나타낸 N이 예를들어 1101(2)라고 하면, 앞에서 부터 1이면 행렬을 제곱 후 한 번 더 곱해준다, 0일 경우 제곱만 한다.
• 1101(2)의 경우 십진수로 나타내면 13이다. 처음의 경우 0제곱상태로 가정하고 위의 과정을 적용하면 

 

[전체 소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

long long N, B;
vector<vector<long long>> origin;

vector<vector<long long>> multiple(vector<vector<long long>>& A, vector<vector<long long>> &B)
{
	vector<vector<long long>> result(2, vector<long long>(2, 0));

	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			long long sum = 0;
			for (int k = 0; k < 2; k++)
			{
				sum += (A[i][k] * B[k][j]) % mod;
			}
			result[i][j] = sum % mod;
		}
	}

	return result;
}

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

	cin >> B;

	string bit;
	while (B) 
	{ 
		bit.push_back((B % 2) + '0'); B /= 2; 
	}
	reverse(bit.begin(), bit.end());

	vector<vector<long long>> ans(2, vector<long long>(2, 0));
	ans[0][0] = 1; ans[0][1] = 0; ans[1][0] = 0; ans[1][1] = 1;

	origin.resize(2); for (int i = 0; i < 2; i++) origin[i].resize(2);
	origin[0][0] = 1; origin[0][1] = 1; origin[1][0] = 1; origin[1][1] = 0;

	for (int i = 0; i < bit.size(); i++)
	{
		ans = multiple(ans, ans);
		if (bit[i] == '1') ans = multiple(ans, origin);
	}

	cout << ans[1][0] % mod;
}

행렬 곱셈 , 피보나치 수가 합쳐진 환장의 문제

굳