[BOJ 1003] 피보나치 함수 (C++)

피보나치 함수 (Silver 3)

문제

전체 문제 보기

1003번: 피보나치 함수

접근법

이 문제는 피보나치 함수를 조금 변형한 형태로 f(n)을 호출했을 때 f(0)과 f(1)이 각각 몇 번 호출되는지 구하는 문제이다. 피보나치는 무식하게 계산할 경우 \(O(2^n)\)이기 때문에 계산 결과를 저장하는 동적 계획법으로 접근해야한다. 동적계획법으로 풀 경우 \(O(n)\)로 풀이가 가능하다. 점화식을 살펴보면 다음과 같이 피보나치수열 와 동일하다.

 

\[f(n) = f(n-1) + f(n-2)\]

구현

 

이 점화식을 0과 1에 같이 적용하여 다음과 같은 코드를 작성할 수 있다.

#include <iostream>
#include <array>
using namespace std;

int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int T;

    array<array <int, 2>, 41> dp{};

    dp[0][0] = 1;    // f(0)일 때 0의 개수
    dp[1][1] = 1;    // f(1)일 때 1의 개수

    cin >> T;
    for (int i = 2; i < 41; i++)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
        dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
    }
    while (T--)
    {
        int N;
        cin >> N;
        cout << dp[N][0] << " " << dp[N][1] << endl;
    }

    return 0;
}

그런데 출력 결과를 살펴보면 d[n][1] 은d[n+1][0]과 동일함을 확인할 수 있다.

▲ 0부터 9까지 순서대로 입력한 결과

피보나치의 점화식에서 똑같은 값을 중복해서 계산하고 있었던 것이다. 따라서 다음과 같이 계산 횟수와 공간 사용을 반으로 줄일 수도 있다. (다만, 해당 문제에서는 N의 최댓값이 40으로 너무 작아서 실제 차이는 거의 없다.)

#include <iostream>
#include <array>
using namespace std;

int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int T;

    int dp[42] = {};

    dp[0] = 1;
    dp[1] = 0;

    cin >> T;
    for (int i = 2; i < 42; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    while (T--)
    {
        int N;
        cin >> N;
        cout << dp[N] << " " << dp[N+1] << endl;
    }

    return 0;
}