BOJ - 11444 피보나치 수 6 해결 전략 (C++)

• 문제 링크
  백준 11444번 - 피보나치 수 6

해결 전략

  문제의 n 입력이 1,000,000,000,000,000,000까지 가능하다. 이는 long long에만 들어갈 수 있는 정수이므로, long long으로 변수를 다뤄야 한다.

  피보나치 수를 다루는 전통적인 방법들을 떠올려 보면, Dynamic Programming으로 다루기엔 선형 반복문을 사용한다고 해도 시간 초과는 너무 뻔하다.

  그 외에 탐색이 필요한 문제는 아니므로, 이 문제는 Divide & Conquer 문제임을 금새 알아차릴 수 있다. 이제 관건은 어떤 수식을 기반으로 분할할 것이냐인데, 이 '수식'을 찾기가 어려운 문제이다. 가장 간단한 피보나치 수열 점화식은 다음과 같은데,

F[n+2] = F[n+1] + F[n]

  이 수식으로는 수 제한을 절대 커버할 수 없음은 설명할 필요도 없다. 새로운 수식을 도출해야한다. 본인은 최초 시도에서 이 수식을 정확히 찾지 못하여 결국 해결에 실패했다. 아쉬운 것이, 거의 다 왔는데, 찾지 못했다는 점이다.

  우리는 본능적으로 저만큼의 수 제한은 2로 분할하는 것 외에는 별다른 풀이가 힘듦을 알 수 있다. 이를 위해서 본인은 다음과 같이 기본 점화식을 전개해보았다.

F[n] = F[n-1] + F[n-2]
F[n] = F[n-1] + F[n-2] + F[n-2] + F[n-3] = 3F[n-2] + 2F[n-3]
F[n] = 5F[n-3] + 3F[n-4]
F[n] = 8F[n-4] + 5F[n-5]
F[n] = F[k+1]F[n-k] + F[k]F[n-k-1]

~> F[n] = F[n/2+1]F[n/2] + F[n/2]F[n/2-1]
~> F[2n] = F[n+1]F[n] + F[n]F[n-1] = F[n]x(F[n+1] + F[n-1])
		 = F[n]x(2F[n-1] + F[n])		// 짝수일때

~> F[2n+1] = F[n+1]^2 + F[n]^2

F[2n] = F[n]x(2F[n-1] + F[n])
F[2n+1] = F[n+1]^2 + F[n]^2

  이 두 식을 도출할 수 있다. 본인은 이 부분에서 F[2n] 식은 구했으나 F[2n+1]을 계속 실수하여 못 구해 해결하지 못하였다. 좀 더 침착한 식 전개 능력이 필요해보인다.

  계속 해보자. 두 식을 n에 대해 나타내면 다음과 같다.

F[n] = F[n/2]x(2F[n/2-1] + F[n/2])
F[n] = F[(n+1)/2]^2 + F[(n-1)/2]^2

  이제 80%는 해결하였다. 이제 몇 가지 분할정복 스킬이 필요한 순간이다.

  F가 분할정복 호출 함수라고 한다면,
1) F가 너무 잦게 호출되므로, 필요한 F 값들을 한번씩만 호출해 값을 기억해 사용하도록 하자.
2) n이 천억까지 가능하므로, 메모이제이션을 해야 할 것으로 느껴진다.
~> map stl을 도입하여, F값이 하나 계산될 때마다 map에 삽입한다. 그리고, 해당 값이 다시 필요할 경우(count 내장 함수를 통해 확인 가능) 재귀 호출을 하지 말고, 이미 사용된 정보를 재사용한다. map에 대한 정보는 구글링을 통해 알아볼 수 있다.

  이러한 아이디어로 본 문제를 해결할 수 있다. PS 테스트 시 이러한 수학 수식 문제가 나올 경우, 차분히 수식을 전개해 분할 정복이 가능하도록 식을 만들 수 있도록 많은 연습을 하자.

  아래는 코드이다.

#include <iostream>
#include <map>
// BOJ - 11444 Fibonacci Number 6
#define DIV		1000000007LL
using namespace std;

map<long long, long long> f;

long long fibo(long long n) {	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 1;
	if (f.count(n) > 0) return f[n];

	if (n % 2 == 0) {
		long long m = n / 2;
		long long temp1 = fibo(m - 1); long long temp2 = fibo(m);
		f[n] = ((2LL * temp1 + temp2) * temp2) % DIV;
		return f[n];
	}
	long long m = (n + 1) / 2;
	long long temp1 = fibo(m); long long temp2 = fibo(m - 1);
	f[n] = (temp1 * temp1 + temp2 * temp2) % DIV;
	return f[n];
}

int main(void) {
	long long n;

	cin >> n;
	cout << fibo(n);

	return 0;
}
*/