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

문제

 

---

풀이

 

동적계획법의 입문(?) 문제이다.

정확히 말하자면 찐 입문은 재귀 함수로 구현된 피보나치 함수를 동적계획법으로 구현하는 것인데...거의 같은 구조이다.

 

n>1 일 때 fib(n) = fib(n-1) + fib(n-2)이다.

그렇다면 fib(n)에서 0이 호출된 횟수는? 당연히 fib(n-1)에서 0을 호출한 횟수와 fib(n-2)에서 0을 호출한 횟수를 더한 값일 것이다.

1이 호출된 횟수 역시 마찬가지일 것이고...

---

소스코드

 

#include <iostream>
using namespace std;

void fibo_cnt(int num) {
    int zero_cnt[41] = { 0, };
    int one_cnt[41] = { 0, };
    for (int i = 0; i <= num; i++) {
        if (i == 0) {
            zero_cnt[i] = 1;
            one_cnt[i] = 0;
        }
        else if (i == 1) {
            zero_cnt[i] = 0;
            one_cnt[i] = 1;
        }
        else {
            zero_cnt[i] = zero_cnt[i - 1] + zero_cnt[i - 2];
            one_cnt[i] = one_cnt[i - 1] + one_cnt[i - 2];
        }
    }
    cout << zero_cnt[num] << ' ' << one_cnt[num] << '\n';
}

int main() {
    int T;

    cin >> T;
    int* N = new int[T];
    for (int i = 0; i < T; i++)
        cin >> N[i];
    for (int i = 0; i < T; i++)
        fibo_cnt(N[i]);
}