피보나치 수 6

음.. 솔직히 저한테는 좀 어려웠습니다. 이게 어떻게든 될거라는 생각을 가지고서, 수를 쭉 나열해보고 하나씩 해보려고 했는데 다행히도 수학적으로 뭔가 수를 줄일때 보통 2에 집중하죠?

그냥 대충 이분탐색, 이분트리 등등 속도를 높이기 위해서 반반 나눠가면서 하는 것들이 생각나더라구요. 또 이제 피보나치 수는 덧셈으로 이뤄져있으니까 뭔가 중간에 곱셈으로 다 처리하는게 가능하지 않을까?

라고 생각해서 열심히 해봤는데 처음에는 당연히 보이지도 않고, 정말 힘들었습니다. 수식으로 증명을 해보려고 했는데도 일단 뭐가 맞는지도 몰라요.

세상에 진짜 그러다가 하나가 보이기 시작합니다.

n이 현재 피보나치 수의 순서일 때,

a = (n/2)
b = (n/2+1)

fibo(n) = fibo(a)^2 + fibo(b)^2

요런게 보입니다. 그래서 와 진짜 이게 되누 ㅋㅋ

이러고 바로 해보려고 했다가 갑자기 다시 머리가 띵합니다… 이걸로는 TO(Time out)을 피할 수 없을거다.. 라고 생각이 들었거든요.

그러고 다시 에.. 열심히 규칙을 찾았습니다…

진짜 힘들었습니다… 역시 수학은 열심히 해놓는게 제일 좋은 거 같아요. ps도 열심히 해야겠지만 일단 수학도 열심히 해야겠습니다. 아 물리도요!

제가 어떤 일이 있었는지.. 한 도화지 1장 정도 사용했는데요. 그렇게 막 많이 사용하진 않았고, 보통 머리로 그려서 해봤씁니다.

그 외로 이제 한번 방문한 곳은 아예 바로 저장해서 바로 반환하도록 하면 TO를 피할 수 있어요!

(또 제가 악필이라 막 많이 적으면서 하는거는 머리가 아플때 주로 쓰고 풉니다.)#

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;
ll MOD = 1'000'000'007;

map<ll, ll> dp;



ll solution(ll n){
    if(dp.find(n) != dp.end()) return dp[n];
    ll result;
    
    ll a, b;
    a = solution(n/2);
    b = solution(n/2+1+(-2 *!(n%2)));
    if(n%2) result = ((a * a)%MOD + (b * b)%MOD)%MOD;
    else result = ((((2*b)%MOD + a)%MOD)*a)%MOD;
    dp[n] = result;
    return result;
}

int main() {
    ll n;
    cin >> n;
    
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    
    cout << solution(n);
    
    

    return 0;
}