문제 정보

제한

• 시간 제한 : 1초(추가 시간 없음)
• 메모리 제한 : 128MB

알고리즘 분류

• 수학
• 구현

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 F(n) = F(n-1) + F(n-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은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

<예제 입력 1>

10

<예제 출력 1>

55

풀이

다이나믹 프로그래밍(DP)의 가장 대표적인 문제라고 할 수 있는 문제이다.

규칙에 맞게 피보나치 수를 구해서 출력하기만 하면 되는 간단한 문제이다.

피보나치 수는 앞의 두 수의 합이므로 fib(a)가 a번째 피보나치 수라고 가정하였을 때,

fib(a) = fib(a-1) + fib(a-2)가 된다.

따라서, 다음과 같이 재귀형으로 함수를 호출하며 피보나치 수를 구할 수 있다.

#include <iostream>
using namespace std;

int fib(int a) {

    switch (a)
    {

    case 0:
        return 0;
        break;

    case 1:
        return 1;
        break;


    default:
        return fib(a-1) + fib(a-2);
        break;
    }

}

int main() {

    int a;

    cin >> a;

    cout << fib(a);

    return 0;
}

위 예제를 실행하고 1, 2, 3, 4 등을 입력하면 정상적으로 1, 1, 2, 3이 출력되는것을 확인할 수 있다.

하지만, 문제의 입력 조건의 최댓값으로 주어진 45를 입력해보자.

문제의 답이 출력되긴 하지만, 제한시간인 1초를 훨씬 넘겨서 뒤늦게 답이 출력되는 것을 볼 수 있다.

따라서 위의 예제처럼 작성하여 제출하게 되면 다음처럼 제한시간이 초과된다.

그 이유는, 피보나치 수를 계산하는 과정에서 했던 계산을 계속하기 때문이다.

fib(10)을 예로 들어보자.

fib(10) = fib(9) + fib(8)

fib(10) = (fib(8) + fib(7)) + (fib(7) + fib(6))

fib(10) = ((fib(7) + fib(6)) + (fib(6) + fib(5)) + ((fib(6) + fib(5)) + (fib(4) + fib(3))

...후략

계산은 아직 절반도 하지 않았는데, fib(8)은 2번, fib(7)은 3번, fib(6)은 4번이나 호출되었다.

시간이 초과되지 않기 위해서는, 조금 근본적인 방법으로부터 접근할 필요가 있다.

#include <iostream>
using namespace std;

int main() {

    long long a[1000] = {0, 1, };

    int count;

    cin >> count;

    for (int i = 2; i <= count; i++)
    {

        a[i] = a[i-1]+a[i-2];

    }

    cout << a[count];

    return 0;
}

위의 코드는 1차원 배열을 통해 함수를 재귀호출하지 않고 피보나치 수를 구한다.

배열의 크기는 상관없기에 넉넉하게 잡았으며, 배열 안에 들어갈 수는 integer의 범위를 벗어날 수도 있기에 long long으로 설정해주었다.

이 예제를 실행하고 45번째 피보나치 수를 구해도, 심지어 100번째 피보나치 수를 구한다 하더라도 즉각 답을 출력해주는 것을 볼 수 있다.