[백준] 1003번 피보나치 함수

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

1003번: 피보나치 함수

1. 문제 접근

문제에서 주어진 fibonacci(N)함수가 호출하는 fibonacci(0)과 fibonacci(1)의 횟수를 출력하는 문제이다. fibonacci(N) = fibonacci(N-1) + fibonacci(N-2) 이므로 fibonacci(N)이 fibonacci(0)와 fibonacci(1)을 호출하는 횟수는 아래와 같이 식을 만들어 볼 수 있다.

 

fibonacci(N)이 fibonacci(0)을 호출하는 횟수

        = fibonacci(N-1)이 fibonacci(0)을 호출하는 횟수 + fibonacci(N-2)가 fibonacci(0)을 호출하는 횟수

fibonacci(N)이 fibonacci(1)을 호출하는 횟수

        = fibonacci(N-1)이 fibonacci(1)을 호출하는 횟수 + fibonacci(N-2)가 fibonacci(1)을 호출하는 횟수

 

또한 매번 새롭게 계산하는 것을 막고자 다이나믹 알고리즘을 사용하여 이미 계산이 완료가 되었다면 저장후 다음에 계산없이 바로 사용할 수 있도록 하였다. 예를 들어 "fibonacci(N-1)이 fibonacci(0)을 호출하는 횟수"를 이전에 이미 계산하여 어딘가에 저장해 놓았다면 "fibonacci(N)이 fibonacci(0)을 호출하는 횟수"를 구할때, 해당 값을 바로 사용하면 된다.

 

시간복잡도 계산

다이나믹 알고리즘을 사용하였으므로 N이 2~40일때의 값만 한번씩 구해준다면 다음 계산에서는 이미 계산된 값들을 이용하여 O(1)시간에 문제를 해결할 수 있다. 즉, 아래 코드에서 setFiboCount(fiboCount, 2) ~ setFiboCount(fiboCount, 40) 함수가 한번씩만 호출되어 fiboCount[2] ~ fiboCount[40]에 적절한 값을 저장해주면 다음 계산부터는 O(1)시간에 문제를 계산할 수 있다는 것이다. 따라서 시간복잡도는 아래와 같으며 주어진 시간 0.25초는 매우 넉넉한 시간이 된다.

시간복잡도 = O(40 - 2 + 1) = O(39)

 

 

 

2. 코드

#include<iostream>
using namespace std;

#define MAX_N 40
#define INIT_COUNT -1

struct FiboCount {
    int fibo0;
    int fibo1;
    void set(int f0, int f1) {
        fibo0 = f0;
        fibo1 = f1;
    }
};

void initFiboCount(FiboCount* fiboCount, int size) {
    fiboCount[0].set(1, 0);
    fiboCount[1].set(0, 1);
    for (int i = 2; i < size; i++)
        fiboCount[i].set(INIT_COUNT, INIT_COUNT);
}

void setFiboCount(FiboCount* fiboCount, int n) {
    if (fiboCount[n].fibo0 != INIT_COUNT)
        return;
    setFiboCount(fiboCount, n - 1);
    setFiboCount(fiboCount, n - 2);
    fiboCount[n].fibo0 = fiboCount[n - 1].fibo0 + fiboCount[n - 2].fibo0;
    fiboCount[n].fibo1 = fiboCount[n - 1].fibo1 + fiboCount[n - 2].fibo1;
}

int main() {
    FiboCount fiboCount[MAX_N + 1];
    initFiboCount(fiboCount, MAX_N + 1);

    int T, N;
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> N;
        setFiboCount(fiboCount, N);
        cout << fiboCount[N].fibo0 << " " << fiboCount[N].fibo1 << endl;
    }

    return 0;
}