[백준] 피보나치 함수

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

1003번: 피보나치 함수

dp를 이용한 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 문제에서 주어진 함수처럼 피보나치 수를 구할 떄, f(1)과 f(0)의 호출 횟수를 출력해야 하는 문제입니다.

 

<Solution>

간단하게 1의 호출 횟수를 저장하는 dp array와 0의 호출 횟수를 저장하는 dp array를 만들어 두고, 그 array에 대해 피보나치 수열을 진행하면 됩니다.

 

간단한 예시로, f(5)가 호출 되면, 이 때 0의 호출횟수와 1의 호출 횟수는 f(4)에서의 횟수 + f(3)에서의 횟수 이기 때문입니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstdio>

int g_dp0[41];
int g_dp1[41];

int main(){
    int N;
    std::cin >> N;
    std::cin.ignore();

    // initialize dp table
    g_dp0[0] = 1;
    g_dp1[0] = 0;
    g_dp0[1] = 0;
    g_dp1[1] = 1;

    for(int i = 2; i<41; ++i){
        g_dp0[i] = g_dp0[i-1] + g_dp0[i-2];
        g_dp1[i] = g_dp1[i-1] + g_dp1[i-2];
    }

    int tmp;
    for(int i = 0; i<N; ++i){
        std::cin >> tmp;
        std::cin.ignore();
        printf("%d %d\n", g_dp0[tmp], g_dp1[tmp]);

    }
    return 0;
}