백준/Silver/1003. 피보나치 함수

#include <iostream>
using namespace std;

int d[100]{0, 1};

int DpFibo(int n) {
    if (n == 1 || n == 0) return d[n];
    if (d[n] != 0) return d[n];
    return d[n] = DpFibo(n - 1) + DpFibo(n - 2);
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int t;
        cin >> t;
        if (!t)
            printf("1 0\n");
        else
            printf("%d %d\n", DpFibo(t - 1), DpFibo(t));
    }
    return 0;
}

일반적 재귀로 풀면 시간초과가 발생해서 dp memoization 방식으로 다시 풀었다.
단순히 피보나치의 특성 상 n이라는 숫자에 0과 1을 출력하는 횟수는 fibo(n-1) , fibo(n)과 같기에 피보나치를 dp로 바꾸고, print에서 n-1, n 2개를 이용해 출력한다.

백준은 재미없다..