[C++] 백준(BAEKJOON) 1003

#include <iostream>
 
int n;
int cache[41];
 
int fibonacci(int x) {
    if (x == 0) 
        return 0;
        
    if (x == 1 || x == 2) 
        return 1;
        
    if(cache[x])
        return cache[x];
        
    return cache[x] = fibonacci(x - 2) + fibonacci(x - 1);
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i) {
        int number;
        scanf("%d", &number);
        if (number == 0) 
            printf("1 0\n");
        else 
            printf("%d %d\n", fibonacci(number - 1), fibonacci(number));
    }
 
    return 0;
}