[C/C++] 백준 11444번 - 피보나치 수 6 (점화식, 분할 정복)

 

<코드>

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

typedef vector<vector<long long>> matrix;
const long long mod = 1000000007;

long long n;

matrix operator * (matrix& a, matrix& b)
{
	matrix c(2, vector<long long>(2));

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++){
			for (int k = 0; k < 2; k++)
				c[i][j] += a[i][k] * b[k][j];

			c[i][j] %= mod;
		}
	return c;	
}

int main()
{
	cin >> n;

	matrix ans = {{1,0}, {0,1}};
	matrix a = {{1,1}, {1,0}};

	while (n > 0)
	{
		if (n % 2 == 1)
			ans = ans * a;
		a = a * a;
		n /= 2;
	}
	
	cout << ans[0][1] << '\n';
}

 

풀이 방법

cocoon1787.tistory.com/308

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

cocoon1787.tistory.com/307

[C/C++] 백준 9471번 - 피사노 주기

이번 문제의 경우 백준 2749 - 피보나치 수 3과 같은 문제이지만 피사노 주기를 이용하여 풀이를 할 수 없습니다. 따라서 피보나치의 점화식을 행렬의 곱셈을 통해 분할 정복으로 풀이를 해야 합니다.

피보나치수열의 점화식은 위와 같고 정리하면 아래와 같이 나타낼 수 있습니다.

 

matrix operator * (matrix& a, matrix& b)
{
	matrix c(2, vector<long long>(2));

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++){
			for (int k = 0; k < 2; k++)
				c[i][j] += a[i][k] * b[k][j];

			c[i][j] %= mod;
		}
	return c;	
}

 

연산자 오버 로딩을 통해 2차원 벡터로 정의된 두 행렬을 파라미터로 받아 두 행렬을 곱한 결과를 리턴해주는 함수입니다. 매 연산마다 자료형을 넘기지 않기 위해서 mod로 나머지를 저장합니다.

matrix는 vector<vector<long long>>의 별칭(type define)입니다.

 

int main()
{
	cin >> n;

	matrix ans = {{1,0}, {0,1}};
	matrix a = {{1,1}, {1,0}};

	while (n > 0)
	{
		if (n % 2 == 1)
			ans = ans * a;
		a = a * a;
		n /= 2;
	}
	
	cout << ans[0][1] << '\n';
}

ans 2차원 벡터는 정답을 저장할 배열이고 초기값으로 단위행렬로 지정합니다. 그리고 a는 곱해줄 행렬입니다. while문은 분할 정복으로 행렬 곱셈을 하는 것이고 연산자 오버 로딩을 통해 (ans = ans * a), (a = a * a)과 같이 행렬의 곱셈을 편하게 할 수 있습니다.  

 

연산자 오버 로딩의 개념이 어려우신 분은 아래의 코드를 보시면 되겠습니다. 모두 같은 코드입니다.

#include<iostream>
#include<vector>
using namespace std;
const long long mod = 1000000007;

long long n;

vector<vector<long long>> multiple (vector<vector<long long>>& a, vector<vector<long long>>& b)
{
	vector<vector<long long>> c(2, vector<long long>(2));

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++){
			for (int k = 0; k < 2; k++)
				c[i][j] += a[i][k] * b[k][j];

			c[i][j] %= mod;
		}
	return c;	
}

int main()
{
	cin >> n;

	vector<vector<long long>> ans = {{1,0}, {0,1}};
	vector<vector<long long>> a = {{1,1}, {1,0}};

	while (n > 0)
	{
		if (n % 2 == 1)
			ans = multiple(ans, a);
		a = multiple(a, a);
		n /= 2;
	}
	
	cout << ans[0][1] << '\n';
}

 

 

www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

 

참고한 풀이 - www.acmicpc.net/blog/view/28