[백준 C++] 11444번: 피보나치 수 6

1. 문제

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

11444번: 피보나치 수 6

 

2. 알고리즘 분류

• 수학
• 분할 정복을 이용한 거듭제곱

 

3. 소스 코드

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<long long>> matrix;
int MOD = 1000000007;

// 행렬 곱셈 정의
matrix operator*(matrix& a, matrix& b)
{
	matrix temp(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++)
			{
				temp[i][j] += a[i][k] * b[k][j];
			}
			temp[i][j] %= MOD;
		}
	}

	return temp;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// n 값 입력
	long long n;
	cin >> n;

	// 분할 정복을 이용한 거듭제곱을 위해 행렬 2개 정의
	matrix ans = { {1, 0}, {0, 1} };
	matrix a = { {1, 1}, {1, 0} };
	
	// 반씩 나눠가면서 빠르게 계산
	while (n > 0)
	{
		if (n % 2 == 1) // 나머지가 1이면, ans에 곱하기
			ans = ans * a;

		a = a * a; // 거듭제곱 해나가기
		n /= 2;
	}

	// 최종 답 출력
	cout << ans[0][1] << '\n';

	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) typedef 키워드

// typedef 키워드를 통해
// 매번 vector<vector<long long>> 명시할 필요없이 단순히 matrix로 표현할 수 있다.
typedef vector<vector<long long>> matrix;

// 분할 정복을 이용한 거듭제곱을 위해 행렬 2개 정의
matrix ans = { {1, 0}, {0, 1} };
matrix a = { {1, 1}, {1, 0} };

 

 2) 연산자 오버로딩

// operator 키워드를 통해
// 해당 값 형식의 연산을 재정의 할 수 있다.(연산자 오버로딩)
matrix operator*(matrix& a, matrix& b)
{
	matrix temp(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++)
			{
				temp[i][j] += a[i][k] * b[k][j];
			}
			temp[i][j] %= MOD;
		}
	}

	return temp;
}

 

  3) 분할 정복을 이용한 거듭 제곱

// 반씩 나눠가면서 빠르게 계산
while (n > 0)
{
	if (n % 2 == 1) // 나머지가 1이면, ans에 곱하기
		ans = ans * a;

	a = a * a; // 거듭제곱 해나가기
	n /= 2;
}