20.06.14 Baekjoon - 피보나치 수 6

내용에 앞서 글을 작성하는 이유를 간단히 적습니다.

 

몇 주 전, 여러 회사에 입사 지원서를 넣었고 그 중 한 회사의 온라인 코딩 테스트를 오늘 보게 되었습니다.

알고리즘에 대해서는 기본은 한다고 생각을 했는데 오늘 큰 실수를 두번 하여 4문제 중 2문제 밖에 맞추지 못했습니다.

이에 상당한 충격과 조금은 현실 직시를 하게 되었습니다.

 

원래는 화요일에 Baekjoon 사이트에서 모의 테스트를 한달에 한번 보려고 계획 했습니다만,

조금 더 시간을 투자해야 할 것 같아 월요일부터 토요일까지 하루에 한문제씩 풀어보려 합니다.

 

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

11444번: 피보나치 수 6

오늘 푼 문제는 [피보나치 수 6]입니다.

10^18 번째까지의 피보나치수를 1초 안에 연산하는 문제였습니다.

예전에 한번 풀어보려 했으나 실패하고, 그저께 다시 한번 도전 했다가 실패하고 오늘에서야 성공한 문제입니다.

 

처음에는 단순히 DP로 해결을 할 수 있을 줄 알았습니다.

하지만 이를 담을 수 있는 배열을 선언할 수 없어 DP를 사용할 수 없었습니다.

 

그 다음에는 실력 좋은 선배에게 조언을 구했습니다.

그러자 선배가 "피보나치에 메모리는 2개면 충분하다."라고 귀뜸해줬습니다.

아래차 항에서부터 윗차 항까지 연산을 하면서 덮어 쓰면 되기 때문입니다.

하지만 1초 안에 모든 연산을 할 수 없었습니다.

 

오늘은 위 두가지를 모두 실패하고

피보나치 수열의 윗차항에서 아랫차항으로 내려가면서 풀어내리면서 규칙을 찾아보았습니다.

그러자 한가지 규칙이 보였습니다.

피보나치 수열을 f(i)라 했을 때, 

 

f(n) = f(n -1) + f(n - 2) = 2f(n - 2) + f(n - 3)  = 3f(n - 3) + 2f(n - 4)..

이 때 

f(1) = f(2) = 1, f(3) = 2, f(4) = 3이므로 이를 위 식에 대입하면

f(n) = f(2)f(n - 1) + f(1)f(n - 2) = f(3)f(n - 2) + f(2)f(n - 3) = f(4)f(n - 3) + f(3)f(n - 4)...

이렇게 변합니다.

 

즉 f(n) = f(k + 1)f(n - k) + f(k)f(n - k - 1)이라는 식이 나옵니다.

이 때 연산을 가장 적게 할 수 있는 방법은 binary search. 즉 k = n / 2일 때입니다.

 

위 연산을 재귀함수로 풀고, memory로 set을 사용해 [k : f(k)]를 저장해 연산 횟수를 줄였습니다.

10^18승일 때 최대 연산이 540회만 발생하는 것입니다.

이 덕분에 오늘에서야 문제를 해결할 수 있었습니다.

 

코드를 보고 싶으신 분들은 아래 접은 글을 풀어서 보십시오.

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

const unsigned int FIBOLIMIT = 1000000007;

unsigned long long getFibo(map<unsigned long long, unsigned long long>& fibo, unsigned long long n)
{
    unsigned long long half = (unsigned long long)(n / 2);
    auto index = fibo.find(n);
    if (index != fibo.end())
    {
        return index->second;
    }
    else
    {
        unsigned long long a = (getFibo(fibo, half + 1) % FIBOLIMIT);
        unsigned long long b = (getFibo(fibo, n - half) % FIBOLIMIT);
        unsigned long long c = (getFibo(fibo, half) % FIBOLIMIT);
        unsigned long long d = (getFibo(fibo, n - half - 1) % FIBOLIMIT);
        fibo.insert(make_pair(n, (a * b + c * d) % FIBOLIMIT));
        return fibo[n];
    }
}

int main()
{
    unsigned long long n;
    map<unsigned long long, unsigned long long> fibo;
    fibo.insert(make_pair(0, 0));
    fibo.insert(make_pair(1, 1));
    fibo.insert(make_pair(2, 1));
    cin >> n;
    cout << getFibo(fibo, n) << endl;;
    return 0;
}