(C++) 백준 1003번 - 피보나치 함수

https://www.acmicpc.net/problem/1003

문제

> 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이 각각 몇 번 출력되는지 구해라.

접근

피보나치 수열은 DP를 사용하여 구현하는 문제다. DP를 사용하여 문제의 코드를 이용하면 된다.

문제해결

> DP를 이용해 fibonacchi[0]과 fibonacchi[1]을 통해 N이 0<= N <=40 이므로 해당 수에 대한 경우를 모두 구한다.
> N에 대해 각각 0과 1이 나오는 수를 나열해 규칙을 찾아보면 0은 fibonacchi[N-1]개 나오고, 1은 fobonacchi[N]개 나온다. 따라서 N이 0, 1일 때를 따로처리하고 나머지 경우는 이 규칙으로 출력해주면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int T, N;
    cin >> T;
    vector<int> fibonacchi(41, 0);
    fibonacchi[0] = 0;
    fibonacchi[1] = 1;
    for (int i = 2; i <= 40; i++)
    {
        fibonacchi[i] = fibonacchi[i - 1] + fibonacchi[i - 2];
    }
    while (T--)
    {
        cin >> N;
        if (N == 0)
            cout << 1 << " " << 0 << '\n';
        else if (N == 1)
            cout << 0 << " " << 1 << '\n';
        else
        cout << fibonacchi[N-1]<< " " << fibonacchi[N] << '\n';
    }
}

후기

DP로 각 N에대해 채우는건 쉬웠지만 출력문에서 좀 고민 했다.