(ALGO) 백준 1003번 문제 - 피보나치 함수

1003 문제

간단한 DP 문제이다. pair를 이용해 풀었다.

#include <iostream>
#include <utility>

using namespace std;

pair<int,int> d[40];

pair<int, int> fibo(int N)
{
    if(d[N].first != 0 || d[N].second != 0)
        return d[N];

    if(N == 0)
        d[N] = pair<int, int>(1, 0);
    else if(N == 1)
        d[N] = pair<int, int>(0, 1);
    else
    {
        pair<int, int> p1 = fibo(N-1);
        pair<int, int> p2 = fibo(N-2);

        d[N].first = p1.first + p2.first;
        d[N].second = p1.second + p2.second;
    }

    return d[N];
}
int main()
{
    int T;

    cin>>T;

    while(T--)
    {
        int N;
        cin>>N;
        pair<int, int> p = fibo(N);
        cout<<p.first<<" "<<p.second<<endl;
    }
    return 0;
}