[Gold 2] 11444 피보나치 수 6

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

 

초기 점화식을 사용해 DP로 문제를 해결하고자 하였다.

하지만, 문제 조건 중 N의 최대 값이 1,000,000,000,000,000,000인 것을 알게 되었으며

실제로 DP로 문제 접근 시 시간 초과가 발생 하였다.

 

따라서 이 문제는 DP가 아닌 정복 분할 형태로 해결해야한다.

 

피보나치의 점화식은 다음과 같다.

FIBO[N + 2] = FIBO[N-1] + FIBO[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

 

두 식을 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

 

 

 

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

long long N;
map<long long, long long> f;

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

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    cout<<fibo(N);

}