백준 2749번 - 피보나치 수 3

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

2749번: 피보나치 수 3

 

본격적인 행렬 제곱 DP를 사용한 문제이다.

 

피보나치 수를 구하는 문제는 다이나믹 프로그래밍의 전형적인 문제 유형이다.

대부분 DP를 시작하는 사람들은 피보나치 수를 처음 접하면서 시작한다.

 

이 문제 역시 피보나치 수를 구하는 문제이다.

 

다른 점은 n 제한 하나이다.

 

이 문제의 n제한은 "1,000,000,000,000,000,000"이다.

 

이번에도 이 숫자가 내 통장잔고였으면.. 하지만 이번 건 스케일이 좀 남다르다.

 

내 통장잔고의 문제가 아니라 몇 년치 국가 예산보다 크지 않을까 싶다.

10^18은 조 단위를 훌쩍 뛰어넘는, 해가 10^20이니까 거의 해 단위와 가까운 숫자이다.

 

다시 생각해보면 O(n)으로 구한다면 컴퓨터로 해도 최소 10^10초가 걸린다는 이야기이다.

 

근데 DP를 O(n) 보다 짧은 시간 안에 구할 수 있나? 

 

결론부터 말하면 가능하다.

 

사실 여기부터는 모르면 못 푸는? 알고리즘 스킬이 들어간다.

 

피보나치 수는 아래와 같다.

 

이 공식을 아래와 같이 행렬로 표현이 가능하다.

 

행렬을 풀어써보면 뭐.. 어렵지 않은 공식이다.

어렵지는 않은데 생각해내진 못하는 그런 공식..

 

그럼 이제 k=n이라고 가정해보자.

 

그럼 아래와 같은 공식이 유도된다.

처음에는 잉? 왜?? 물음표*100일 수 있는데 천천히 생각해보면 너무나 당연하다.

 

예를 들어 n = 3이라 가정해보자

 

위의 공식을 사용하면 위와 같다.

그럼 다시 F_2와 F_1을 구해보자.

이때 F_1 = 1이고 F_0 = 0 이므로 정리해보면 아래와 같다.

여기서 유추할 수 있는 건 n이 커지더라도 [ [1 1] [1 0] ] 행렬이 거듭제곱 형태로 표현되겠구나!이다.

 

그럼 다시 일반화해보면 다음과 같다.

 

행렬의 거듭제곱은 분할 정복 기법을 사용하면 O(logn)만에 구할 수 있기 때문에 이제 밑도 끝도 없는, 해에 가까운 연산 역시 1초 안에 구할 수 있게 되었다!

 

(행렬의 거듭제곱은 앞서 포스팅한 문제에 있기 때문에 따로 설명하진 않음)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[2][2] = { {1,1}, {1,0} };
ll rem[2][2] = { {1,1}, {1,0} }; // 고정

void squared(ll a[][2], ll b[][2]) {
	ll temp[2][2];
	memset(temp, 0, sizeof(temp));
	for (ll i = 0; i < 2; i++) {
		for (ll j = 0; j < 2; j++) {
			for (ll k = 0; k < 2; k++) {
				temp[i][j] += a[i][k] * b[k][j];
				temp[i][j] %= 1000000;
			}
		}
	}
	memcpy(arr, temp, sizeof(arr));
}

void reculs(ll x) {
	if (x == 1) return;
	if (x % 2 == 1) {
		reculs(x / 2);
		squared(arr, arr);
		squared(arr, rem);
	}
	else {
		reculs(x / 2);
		squared(arr, arr);
	}
}

int main() {
	ll n;
	cin >> n;
	if (n > 1)reculs(n - 1);
	cout << arr[0][0] << "\n";
}

10830번 문제와 거의 똑같은 코드지만 난이도는 3단계 차이이다.

 

결국 이런 문제를 풀어봤는지 아닌지에 따라 난이도의 차이가 이렇게 벌어지는 게 아닐까 싶다..