BOJ 11444 피보나치 수 6

1 개요

BOJ 11444 피보나치 수 6

• 백준 온라인 저지 11444번 문제
• BOJ 26단계

2 C++

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

map<long, long> M;

long fib(long n) {
	if (n == 0) {
	    return 0L;
	}
	if (n == 1) {
	    return 1L;
	}
	if (n == 2) {
	    return 1L;
	}
    if (M.count(n) > 0) {
        return M[n];
    }
    long t, a, b;
	if (n%2 == 0) {
		t = n / 2;
		a = fib(t-1);
		b = fib(t);
		M[n] = (((2L*a)+b)*b) % 1000000007L;
		return M[n];
	}
	t = (n+1) / 2;
	a = fib(t-1);
	b = fib(t);
	M[n] = ((a*a)+(b*b)) % 1000000007L;
	return M[n];
}

int main() {
	long N;
	cin >> N;
	cout << fib(N);
}