[PS] 피보나치 수 6 / C++ (백준 11444번)

피보나치 수 6 (백준 11444번)

 

문제를 해결하기 위한 수학 식을 만들고, 분할 정복으로 해결할 수 있는 문제로, 식을 만드는 과정에서 n이 짝수일 때, 홀수일 때로 나누는 방법을 떠올리기 쉽지 않았다.

 

풀이 과정

• 다음과 같이 d[i]="i번째 피보나치 수"로 식을 세워서 변형해 보면 다음과 같은 규칙을 찾을 수 있다.

• 이를 이분 탐색을 하며, n이 짝수일 때, 홀수일 때로 나누면 다음과 같이 2개의 식이 나온다.

• 이를 분할 정복으로 구현하되 map을 활용하여 한 번 계산한 fib(n)의 값을 저장해준다. 이렇게 한 번 구했던 fib(n) 값을 중복으로 값을 구하는 상황을 없애주게끔 구현해 주면 이분 탐색 시간 복잡도 * map의 시간 복잡도 = $O(logn) * O(logn)$의 시간 복잡도로 풀 수 있다(=$O(logn)$).

#define MOD 1000000007
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;

map<ll, ll> m;

ll fib(ll n)
{
	if (m.find(n) != m.end())
		return m[n];
	if (n % 2 == 0) {
		ll k = n / 2;
		m.insert({ n, ((fib(k) * fib(k + 1)) % MOD + (fib(k - 1) * fib(k)) % MOD) % MOD });
		return m[n];
	}
	else {
		ll k = (n - 1) / 2;
		m.insert({ n, ((fib(k + 1) * fib(k + 1)) % MOD + (fib(k) * fib(k)) % MOD) % MOD });
		return m[n];
	}
}

int main()
{
	ll n;
	scanf("%lld", &n);
	m.insert({ 0, 0 });
	m.insert({ 1, 1 });
	m.insert({ 2, 1 });
	printf("%lld\n", fib(n) % MOD);
	return 0;
}

 

MOD만 변경해주면 피보나치 수 3(백준 2749번)도 AC를 받을 수 있다!