[Baekjoon, C++] 11444번: 피보나치 수 6

도입

백준 단계별 풀기에서 분할정복 여덟 번째 문제이다.

 

 

백준 11444번 문제, 입력, 출력

---

백준 11444번 입출력 예제 1

---

풀이

1. n이 매우 크다.

  - 점화식으로 푸는 DP 방법 = $O(N)$ -> 비추천

  - 행렬로 변환한 풀이법(행렬 거듭제곱) - $O(M^3 * logN)$ -> 사용  

 

2.1. 점화식을 행렬로 변환해보자.

 

2.2. 여기서 f1 과 f2 는 1이다. 그리고 거듭제곱 결과의 2x2 행렬을 a b c d로 치환하면 

2.3. $F_{n+2} = a+b$ 이고 $F_{n+1} = c+d$가 된다. 

 

 

2.4. 이제 $F_{n}$을 구해보자. n에 n-1을 대입한다. 그렇다면 n-1의 거듭제곱을 구하고 2번째 행의 2개 값을 더해주면 된다.

 

3. 곱셈 연산자 오버로딩을 사용한다. c++에서는 '연산자 오버로딩'을 찾아보면 더 자세한 내용들이 많을 것이다. power함수를 따로 만들어서 분할정복을 따르지 않고, 연산자 오버로딩을 통해 코드를 구성하였다.

---

코드

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

typedef long long LL;
typedef vector<vector<LL>> matrix;
LL p = 1000000007;
LL n;

matrix operator * (matrix& a, matrix& b)
{
	matrix temp(2, vector<LL>(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] %= p;
		}
	return temp;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;

	matrix result = { {1,0}, {0,1} };  // 이차단위행렬 E
	matrix poMat = { {1,1}, {1,0} };  //거듭제곱할 행렬

	while (n > 0)
	{
		if (n % 2 == 1)
			result = result * poMat;
		poMat = poMat * poMat;
		n /= 2;
	}

	cout << result[0][1] << '\n';
}
 

---

마무리

분할정복으로 풀 수 있지만, 연산자 오버로딩을 사용하여 반복문으로 풀었다! 연산자 오버로딩을 새로 접할 수 있는 좋은 경험이 였다.