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

 

 

 

 처음에는 아래와 같은 피보나치 함수의 재귀적 정의를 이용해서 종료 조건인 fibonacci(0) 과 fibonacci(1)이 호출 될 때마다 각각 a와 b의 값을 증가시켜서 호출 횟수를 새려고 하였다. 그러나 n이 커짐에 따라 0과 1의 호출 횟수가 기하급수적으로 증가하여 시간초과가 났다. 그래서 아래와 같은 방법으로는 n이 조금만 커지더라도 사용할 수 없다.

int a;
int b;

int fibonacci(int n) {
	if (n == 0) {
		a++;
		return 0;
	}
	else if (n == 1) {
		b++;
		return 1;
	}
	else {
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

 

  피보나치 수를 계산할 때, 중복되는 호출을 제한하기 위해 동적계획법을 이용하는 방법이 널리 알려져 있다. 예를들어 아래와 같이 fibo(4)를 구하기 위해서 fibo(2)를 두번이나 호출해야 하므로 fibo(2)를 한 번 구하면 이 값을 메모리에 저장해 두었다가 나중에 fibo(2)를 호출하면 이 값을 이용하는 방법이다.

 

fibo(4) = fibo(3) + fibo(2) 

fibo(4) = (fibo(2) + fibo(1))+ fibo(2)

 

 0과 1의 호출 횟수또한 이러한 점화식이 있다면 DP(동적 계획법)으로 더 빠르게 풀 수 있을 것이다. 피보나치 수열의 성질을 조금만 생각해보면 0의 호출 횟수와 1의 호출횟수 또한 피보나치 수열처럼 a(N) = a(N-1) + a(N-2)의 점화식을 갖는 다는 것을 알 수 있다. 

fibo(n) = k	arr_zero(n) = fibo(0) 호출 횟수	arr_one(n) = fibo(1) 호출 횟수
fibo(0) = 0	1	0
fibo(1) = 1	0	1
fibo(2) = fibo(0) + fibo(1) = 2	arr_zero(2) = arr_zero(0) + arr_zero(1) =1	arr_one(2) = arr_one(0) + arr_one(1) = 1
fibo(3) = fibo(1) + fibo(2) = 3	arr_zero(3) = arr_zero(1) + arr_zero(2) =1	arr_zero(3) = arr_zero(1) + arr_zero(2) =2

 

#include <iostream>
using namespace std;
int a = 0;
int  b = 0;
int main()
{
    int n,t;
    cin >> t;
    // arr_zero[i]는 i번 째 피보나치 수열이 호출하는 fibonacci(0)의 갯수
    // arr_one[i]는 i번 째 피보나치 수열이 호출하는 fibonacci(1)의 갯수
    
    int arr_zero[41];
    int arr_one[41];
 
    arr_zero[0] = 1;
    arr_zero[1] = 0;
    arr_one[0] = 0;
    arr_one[1] = 1;
    arr_zero[2] = 1;
    arr_one[2] = 1;
    for (int i = 3; i <= 40; i++) {
        arr_zero[i] = arr_zero[i - 1] + arr_zero[i - 2];
        arr_one[i] = arr_one[i - 1] + arr_one[i - 2];
    }
 
    for (int i = 0; i < t; i++) {
        cin >> n;
        cout << arr_zero[n] << " " << arr_one[n] << endl;
 
    }
    return 0;
}