[BOJ 11444번/C++] 피보나치 수 6

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

11444번: 피보나치 수 6

피보나치 수 6

문제

문제

피보나치 수는 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으로 나눈 나머지를 출력한다.

 

풀이

먼저 입력되는 n의 수가 최대 1,000,000,000,000,000,000 이다. 주어지는 입력값부터 int형 변수에 저장할 수 없는 매우 큰 수이다. 그러니, 입력받는 수는 unsigned long long으로 선언해준다.

 

기존에 동적 계획법으로 풀었던 피보나치 수처럼 1부터 시작해서 피보나치 수를 저장해나가면 시간 초과가 당연히 발생한다.

(\O(n)\) 이내의 방법을 찾아야한다.

 

그러니, (\F(n) = F(n - 1) + F(n - 2)\) 라는 식을 변형시켜보는 시간을 먼저 가져봤다.

마지막 나온 식을 참고해, 짝수일 때와 홀수일 때를 나눠서 수를 분할해서 풀면 (\O(n)\) 보다 빠른 시간으로 풀 수 있다.

 

#include <iostream>
#include <unordered_map>

#define endl '\n'
#define mod 1000000007

using namespace std;

unordered_map<unsigned long long, unsigned long long> F;

unsigned long long fibonacci(unsigned long long n) {
    if (n == 0)
        return F[0];

    if (F[n])
        return F[n];
    
    if (n % 2 == 0) {
        F[n] = ((fibonacci(n / 2) % mod) * ((fibonacci(n / 2 + 1) % mod + fibonacci(n / 2 - 1) % mod) % mod)) % mod;
    }
    else {
        F[n] = ((((fibonacci((n + 1) / 2) % mod) * (fibonacci((n + 1) / 2) % mod)) % mod) + (((fibonacci((n - 1) / 2) % mod) * (fibonacci((n - 1) / 2) % mod)) % mod)) % mod;
    }

    return F[n];
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    unsigned long long n;
    cin >> n;

    F[0] = 0;
    F[1] = F[2] = 1;

    cout << fibonacci(n) << endl;

    return 0;
}

 

해시와 전개식을 통해 풀었는데, 정석 풀이는 행렬을 이용한 풀이인 것 같다(실제로 다른 분들 풀이는 대부분 행렬을 활용한 풀이였다...). 행렬 풀이도 알아봐야할 것 같다.