백준 1003: 피보나치 함수

문제 요약

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

어떠한 피보나치 함수에 대해서 fibonacci(n) (이하 fibo(n))은 fibo(n-1)과 fibo(n-2)를 재귀호출하는 구조이다. 그리고 그렇게 재귀호출 하다가 fibo(0)과 fibo(1)이 호출되는 횟수를 구하는 문제이다.

즉, fibo(n)에서 fibo(1)과 fibo(0)이 호출되는 횟수는 fibo(n-1)과 fibo(n-2)에서 호출되는 횟수의 합과 같다.

이를 구하는 함수를 따로 구현해서, 두 번 돌렸다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int zero[41];
int one[41];

int fiboOne(int n) {
	if (one[n] != -1) return one[n];
	one[n] = fiboOne(n - 1) + fiboOne(n - 2);
	return one[n];
}
int fiboZero(int n) {
	if (zero[n] != -1) return zero[n];
	zero[n] = fiboZero(n - 1) + fiboZero(n - 2);
	return zero[n];
}

int main()
{
	int t, n;

	fill_n(zero, 41, -1);
	fill_n(one, 41, -1);
	zero[0] = 1;
	zero[1] = 0;
	one[1] = 1;
	one[0] = 0;
	cin >> t;
	while (t--) {
		scanf("%d", &n);
		printf("%d %d\n", fiboZero(n), fiboOne(n));
	}
	return 0;
}