백준(Baekjoon)알고리즘 <문제번호 1003> - 피보나치

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {

    if (n == 0) {

        printf("0");

        return 0;

    } else if (n == 1) {

        printf("1");

        return 1;

    } else {

        return fibonacci(n‐1) + fibonacci(n‐2);

    }

}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

풀이

이 문제는 시간 초과가 많이 나는 문제입니다. 왜냐하면 재귀를 하는 과정에서 연산이 기하급수적으로 늘어나기 때문이죠 40까지 계산을 하는 동안에도 실행시간이 길어져서 풀이는 맞더라도 코딩 테스트에서는 탈락할 수 있죠.

그래서 배열에 길이를 한정한 후에 이전에 호출했던 피보나치 함수에 대한 결과를 저장하면서 연산을 줄이는 방법을 선택해야 했습니다. 3이 2와 1을 호출하는 것처럼 n 은 재귀적으로 작동합니다. 

결과는 0과 1에 호출 횟수를 출력하는 문제입니다.

코드

#include  <iostream>
#include  <array>
using namespace std; 
 
int fibonacci(int n) { 
     
    static array<int,40> result; 
 
    if (n == 0) { 
        return 0; 
    } 
    else if (n == 1 || n == 2) { 
        return 1; 
    } 
 
    else { 
        if (result[n] > 0) 
            return result[n]; 
        return result[n] =fibonacci(n-1) + fibonacci(n-2); 
    } 
} 
 
 
int main() 
{ 
    int number{}; 
    int testcase{}; 
 
cin >> number; 
    for (int i = 0; i < number; ++i) 
    { 
        cin >> testcase; 
        if (testcase == 0) 
            cout << 1 << ' ' << 0 << endl; 
        else if (testcase == 1) 
            cout << 0 << ' ' << 1 << endl; 
        else 
            cout << fibonacci(testcase-1) << ' ' << fibonacci(testcase) << endl; 
     
    } 
return 0; 
}