[백준 1003번] [동적 계획법] 피보나치 함수

이 문제는 전형적인 DP문제이다. 다만, 0과 1을 호출하는 갯수를 계산을 하라는 점에서 살짝은 낯설게 느껴질 수 있으나 본질적으로 두 수를 더하는 과정에서 0과 1을 더하는 양상을 각각 구분해서 저장해주는 방식으로 이용해주면 된다는 것을 쉽게 알 수 있다.

 

이 과정에서 가장 처리가 쉬운 방법이 구조체를 이용하는 것이다.

 

추가적으로 피보나치의 경우에는, 같은 계산을 매우 반복해서 해야하는 상황이 등장하게 되므로 DP를 이용하여 이미 존재하는 숫자의 경우에는 계산을 하지 않고 바로 return만 시켜주면 된다.

 

해당하는 방식으로 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef struct{
    int zero;
    int one;
}fib_num;

fib_num fib(int n, vector<fib_num> & fib_store);

int main(void){
    int T;
    cin >> T;

    vector<fib_num> fib_store;
    
    fib_num zero_case;
    zero_case.zero = 1;
    zero_case.one = 0;
    fib_store.push_back(zero_case);

    fib_num one_case;
    one_case.zero = 0;
    one_case.one = 1;
    fib_store.push_back(one_case);

    for (int i = 0; i < T; i++){
        int test_case;
        cin >> test_case;
        fib_num result = fib(test_case, fib_store);
        cout << result.zero << " " << result.one << "\n";
    }

    return 0;
}

fib_num fib(int n, vector<fib_num> & fib_store){
    if (n == 1 || n == 0) return fib_store[n]; //early exit

    if (fib_store.size() > n) return fib_store[n];

    else if(fib_store.size() < n){
        fib(n - 1, fib_store);
    }
    fib_num temp;
    temp.one = fib_store[n - 1].one + fib_store[n - 2].one;
    temp.zero = fib_store[n - 1].zero + fib_store[n - 2].zero;
    fib_store.push_back(temp);
    
    return temp;
}

생각보다는 쉬운 문제였다.