백준 1003 - 피보나치 함수

문제 번호: 1003

문제 제목: 피보나치 함수

문제 주소: https://www.acmicpc.net/problem/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을 입력 받아 위 함수를 실행하였을 때 0이 출력되는 횟수와 1이 출력되는 횟수를 출력한다.

테스트 케이스

3 0 1 3 40

1 0 0 1 1 2 63245986 102334155

문제 풀이

하나의 결과를 출력하는데 소요되는 시간은 얼마 걸리지 않지만, T회의 테스트케이스를 진행하는 과정에서 매번 계산을 새로 하게 될 경우 그만큼 연산을 낭비하게 된다.

n이 입력되는 경우 0이 출력된 횟수는 n-1번째 피보나치 수와 동일하고, 1이 출력된 횟수는 n번째 피보나치 수와 동일하다. 따라서 n번째까지의 피보나치 수를 구하면 각각의 결과를 파악할 수 있다.

다만 T개의 테스트 케이스를 수행하는 것이 이번 문제의 특징이고, 첫 번째 테스트 케이스로 n이 입력된 경우 1~n까지의 결과가 40을 구하는 과정에서 이미 구해지게 되므로, 이들에 대한 정보를 별도로 저장하여 다른 테스트 케이스에서 활용한다면 연산 낭비를 줄일 수 있다. n보다 작은 수인 경우에는 바로 결과가 나오고, n보다 큰 수는 n번째까지의 연산 과정을 생략할 수 있기 때문이다.

1. [0]~[40]까지를 저장할 수 있도록 배열을 생성한다.
2. [0] = 0, [1] = 1로 대입한다.
3. n을 입력받는다.
4. 2~n까지 진행하면서 [i] == 0인 경우에는 [i] = [i - 1] + [i - 2]를 대입한다. 아닌 경우에는 다음으로 넘어간다.
5. 0 호출 횟수와 1 호출 횟수를 출력한다.
6. T회동안 3~5를 반복한다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1003()
{
	int T;
	cin >> T;
	int fib[41] = { 0 };
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 0; i < T; ++i)
	{
		int n;
		int callZero;
		int callOne;
		cin >> n;
		if (n == 0)
		{
			callZero = 1;
			callOne = 0;
		}
		else if (n == 1)
		{
			callZero = 0;
			callOne = 1;
		}
		else
		{
			for (int i = 2; i <= n; ++i)
			{
				if (fib[i] == 0)
				{
					fib[i] = fib[i - 1] + fib[i - 2];
				}
			}
			callZero = fib[n - 1];
			callOne = fib[n];
		}
		cout << callZero << " " << callOne << endl;
	}
	return;
}