[백준] 11444번: 피보나치 수 6

Solved.ac 골드4
https://www.acmicpc.net/problem/11444

설명

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

해결 Tip

알고리즘 분류

• 수학
• 분할 정복을 활용한 거듭제곱

기본적으로 n이 굉장히 크기 때문에 반복문이나 일반 재귀함수로 풀면 안 된다.
n번째 피보나치 수를 F(n)이라고 하면, F(8)은 다음과 같이 나타낼 수 있다.

$F\left(8\right)=F\left(7\right)+F\left(6\right)\\ \ \ \ \ \ \ \ \ \ =2F\left(6\right)+F\left(5\right)\\ \ \ \ \ \ \ \ \ \ =3F\left(5\right)+2F\left(4\right)\\ \ \ \ \ \ \ \ \ \ =5F\left(4\right)+3F\left(3\right)\\ \ \ \ \ \ \ \ \ \ =8F\left(3\right)+5F\left(2\right)\\ \ \ \ \ \ \ \ \ \ =13F\left(2\right)+8F\left(1\right)$

여기서 F 앞의 계수들을 보면 앞 F의 계수는 1, 2, 3, 5, 8, 13, 21 / 뒤 F의 계수는 1, 1, 2, 3, 5, 8, 13 이다.
이 사실을 일반화하면 다음과 같은 계산식을 구할 수 있다.

$F\left(n\right)의\ k번째\ 분해식=F\left(k+1\right)F\left(n-k\right)+F\left(k\right)F\left(n-k-1\right)\\ \therefore n=2k인\ 경우,\ F\left(n\right)=F\left(\frac{n}{2}\right)\left\{F\left(\frac{n}{2}+1\right)+F\left(\frac{n}{2}-1\right)\right\}\\ \ \ \ \ n=2k+1인\ 경우,\ F\left(n\right)={\left\{F\left(\frac{n+1}{2}\right)\right\}}^2+{\left\{F\left(\frac{n-1}{2}\right)\right\}}^2$

이 수식과 dp와 분할정복 알고리즘을 쓰면 문제를 풀 수 있다.

코드

#include <bits/stdc++.h>
#define MOD 1000000007
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

map<long long int, int> stock;

int fibonach(long long int N) {
    if (N <= 0) return 0;
    else if (N == 1 || N == 2) return 1;
    else if (stock.find(N) != stock.end()) return stock[N];
    else {
        if (N % 2) {
            long long a = fibonach(N/2 + 1);
            long long b = fibonach(N/2);

            stock[N] = (a * a) % MOD + (b * b) % MOD;
            return stock[N];
        }
        else {
            long long a = fibonach(N/2 - 1);
            long long b = fibonach(N/2);

            stock[N] = (2*a + b) % MOD * b % MOD;
            return stock[N];
        }
    }
}

int main() {
    fastio;
    stock[0] = 0;
    stock[1] = 1;
    stock[2] = 1;

    long long int N; cin >> N;
    cout << fibonach(N) % MOD;
    return 0;
}