[PS] 백준 1003번 - 피보나치 함수

zeros배열과 ones 배열을 활용하여 각 숫자에서 0과 1이 나온 횟수를 메모이제이션으로 저장한다.

#include <iostream>
#include <vector>

using namespace std;

int zeros[41], ones[41];

int z(int n) {
    if(zeros[n]) return zeros[n];
    else if(n==0) return zeros[n]=1;
    else if(n==1) return zeros[n]=0;
    else return zeros[n]=z(n-1)+z(n-2);
}

int o(int n) {
    if(ones[n]) return ones[n];
    else if(n==0) return ones[n]=0;
    else if(n==1) return ones[n]=1;
    else return ones[n]=o(n-1)+o(n-2);
}

int main() {
    int T;
    cin >> T;
    for(int i=0; i<T; i++) {
        int N;
        cin >> N;
        cout << z(N) << " " << o(N) << endl;
    }
}