백준 1003번: 피보나치 함수 C++ 코드(DP, 다이나믹 프로그래밍)

//1003
#include<iostream>

using namespace std;

struct zeroandone{
    int zero;
    int one;
};

zeroandone array1[41];
int used[41] = {0,};

zeroandone fibo(int n){
    zeroandone temp;
    if(used[n] == 1){
        return array1[n];
    }else if(n == 0){
        temp.zero = 1;
        temp.one = 0;
        return temp;
    }else if(n == 1){
        temp.zero = 0;
        temp.one = 1;
        return temp;
    }else{
        zeroandone temp1 = fibo(n-1);
        zeroandone temp2 = fibo(n-2);
        temp.zero = temp1.zero + temp2.zero;
        temp.one = temp1.one + temp2.one;
        array1[n] = temp;
        used[n] = 1;
        return temp;
    }
}

int main(){
    int n;
    int temp;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> temp;
        cout << fibo(temp).zero << " " << fibo(temp).one << "\n";
    }
}

 

1년동안 접었던 알고리즘을 요새 다시 감을 잡고 있다.

 

이 문제의 핵심은 재귀를 통해 단순히 피보나치 함수를 구하는 것이 아닌 다이나믹 프로그래밍의 메모이제이션을 활용하여 사용한 값을 다시 재활용해서 시간을 줄이는 것이 핵심이다.