문제

피보나치 함수를 푸는 문제를 Recursive하게 구할 때 return 0과 return 1이 되는 수 Count

Idea

return 0이 되는 수와 return 1이 되는 수를 피보나치 수열로 푼다.

단, 문제의 제한 시간이 조금 빡빡한 것 같아서 최대 N인 40까지 입력을 받기 전에 한번에 구해서 vector에 저장한 후, N을 입력받을 때 마다 vector에서 꺼내서 출력하도록 구현

Code

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

#include <vector>
#include <iostream>

constexpr int MAX_N = 40;
constexpr int MAX_VECTOR_SIZE = MAX_N+1;
    //to include 0-th index

void MakeFibVector(std::vector<int>& v0, std::vector<int>& v1){
    v0 = std::vector<int>(MAX_VECTOR_SIZE, 0);
    v1 = std::vector<int>(MAX_VECTOR_SIZE, 0);

    //initialize 0 and 1
    v0[0] = 1;
    v1[0] = 0;

    v0[1] = 0;
    v1[1] = 1;

    //fill 2nd_40th
    for (int i=2; i<MAX_VECTOR_SIZE; ++i){
        v0[i] = v0[i-1]+v0[i-2];
        v1[i] = v1[i-1]+v1[i-2];
    }

    return;
}

int main(){
    int T = 0;
    std::cin >> T;

    std::vector<int> v0;
    std::vector<int> v1;

    MakeFibVector(v0, v1);

    for (int i=0; i<T; ++i){
        int N = 0;
        std::cin >> N;

        std::cout << v0[N] << " " << v1[N] << std::endl;
    }

    return 0;
}