[C++] 2749: 피보나치 수 3

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

 

피보나치 수를 구하는 재미있는 방법을 알게 되어 공유한다.

 

알고리즘 분류

• 분할 정복
• 다이나믹 프로그래밍

 

문제설명

 

 문제는 아주 간단하다. 다만, n이 1e18이다. 일단 n은 long long으로 받아야 한다. 그리고 MOD값은 1e6이므로, 결과값 역시 안전하게 long long으로 받아주자.

 

문제접근

 

우선 피보나치 수열의 점화식은 다음과 같다.

 

이 방법으로 f(n)을 구할 수 있지만, n이 1억을 넘어가기 때문에 시간 초과에 해당한다. 즉 O(logN)으로 풀어야 한다. 그러면 어떻게풀어야할까?

 

O(logN)으로 해결할 수 있는 알고리즘은 많지 않다. 분할 정복 말고는 풀이를 찾기 어려울 것이다. 따라서 이 문제를 분할 정복으로 풀어보자.

 

점화식의 장점은 점화식을 변형시켜서 유용한 해를 구할 수 있다는 점이다. 이제 점화식을 갖고 놀아보자. 

 

이렇게 식을 쓰면서 뭔가 규칙성이 보인다. 바로 앞의 계수 + 뒤의 계수를 해서 그 다음식의 앞 계수가 되고, 앞 계수는 뒤 계수가 된다. 

 

어? 이 계수의 법칙을 우리는 알고 있다. 바로 "피보나치 수"의 도출 방식과 완전히 같다. 즉, 피보나치 수열의 초반부는 다음과 같으므로,

 

따라서 이를 그대로 위 식에 적용해보면,

 

오, 이제 진짜로 규칙성이 보인다. 계수를 피보나치로 나타내면, 앞의 수 + 뒤의 수를 할 수 있다. 그 결과값은 즉,

 

이것과 같다. 이제 우리는 큰 피보나치 넘버를 작은 피보나치 넘버 4개의 곱, 합으로 정의할 수 있다. 이 과정에서 분할 정복을 이용할 수 있다. 물론, 이 상태에서는 1개의 수를 구하기 위해 4개를 구해야 하니 비효율적이다. 최대한 효율적인 분배방식을 찾아야 한다. 이때 분할 정복의 효율을 최대화하려면 n을 n/2에 가깝게 나누어야 한다.

 

 여기에서 최대한 이득을 보기 위해 n이 홀수일 때와 짝수일 때로 구분하자. 그러면 최대한 많은 값을 겹치도록 할 수 있다. 그 결과는 다음과 같다.

 

훌륭하다. 이제 홀수의 경우는 2개의 절반에 가까운 값, 짝수는 3개의 절반에 가까운 값으로 분해할 수 있고, 이걸 분할 정복 알고리즘으로 구하면 된다. 

 

 또한 주목할 점은, 값을 저장하기 위해 배열을 사용할 수 없다. (le18개의 index가 필요) -> 따라서 map을 이용해서, 재귀 dp를 사용하면 답을 구할 수 있다.

 

전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void fastIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

/*
fibonacci 점화식 변형
f(2m+1) = f(m+1)*f(m+1) + f(m)*f(m)
f(2m) = f(m)*f(m+1) + f(m-1)*f(m)
*/

ll n; // ~1e18
map<ll, ll> fibo;
ll MOD = 1e6;

ll go(ll num)
{
  if(num == 0) return 0;

  ll& ret = fibo[num];
  if(ret) return ret;

  vector<ll> v(4,0);
  if(num % 2)
  {
    v[0] = num / 2 + 1;
    v[1] = v[0];
    v[2] = num / 2;
    v[3] = v[2];
  }
  else
  {
    v[0] = num / 2;
    v[1] = num / 2 + 1;
    v[2] = num / 2 - 1;
    v[3] = num / 2;
  }

  ll left, right;
  left = (go(v[0]) * go(v[1])) % MOD;
  right = (go(v[2]) * go(v[3])) % MOD;
  ret = (left + right) % MOD;
  return ret;
}

int main()
{
  cin >> n;
  fibo[0] = 0;
  fibo[1] = 1;
  fibo[2] = 1;
  
  cout << go(n) << endl;
}

 

피보나치 수를 분할 정복으로 구할 수 있다니, 정말 재미있는 발견이다.