1003번 : 피보나치 함수

Backjoon Online Judge 

"1003번 : 피보나치 함수" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/1003

피보나치 함수를 구할 때 특정 함수가 몇번 호출되었는지 알기 위해서는 피보나치 함수를 재귀적으로 구현하여 함수 호출 될 때 마다 함수 호출 횟수를 1씩 증가시키면 됩니다. 하지만 그렇게 구현 할 경우 시간이 오래 걸리기 때문에 점화식을 구하여 쉽고 빠르게 함수 호출 횟수를 구했습니다.

N	fibo(0) 호출	fibo(1) 호출
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

위 표를 보면 fibo(0)의 호출 횟수와 fibo(1)의 호출 횟수도 피보나치 수의 증가와 같이 증가하는 것을 알 수 있습니다. (N = 0일때는 제외)

fibo(0) : 0 1 1 2 3 ...

fibo(1) : 1 1 2 3 5 ...

따라서 피보나치수를 배열을 이용해 빠르게 구하고 N의 값에 따라 그에 맞는 피보나치 수를 fibo(0), fibo(1)의 출력값으로 이용했습니다.

 - fibo(0)의 호출 횟수는 N이 주어질때 fibo(N-1)과 같습니다.

 - fibo(1)의 호출 횟수는 N이 주어질때 fibo(N)과 같습니다.

(표를 보고 규칙을 유추)

코드는 C++로 작성하였습니다.

#include <iostream>
 
#define MAX 40
 
using namespace std;
 
int main() {
    int T, N;
    cin >> T;
    int fibo[MAX] = { 0,1 };
 
    while (T--) {
        cin >> N;
        if (N == 0) {
            cout << "1 0\n";
            continue;
        }
        
        for (int i = 2; i <= N; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }
        
        cout << fibo[N - 1] << " " << fibo[N] << "\n";
    }
    return 0;
}