백준 1003번: 피보나치 함수

백준 온라인 저지(BOJ) 1003번 문제

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

1. 문제 요약

주어진 코드로 피보나치 수를 구할 때, base case가 몇 번 호출되는지 구하기

2. 알고리즘

2-1. 기본적인 생각

전역 변수를 만들어서 해당 영역이 호출될 때마다 더해주면 간단하다.

그런데 N이 40 정도 될 경우 1억 번 정도를 더하게 되는데, 시간 낭비가 상당하다.

2-2. 재귀적 성질 이용하기

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)이므로

1 이상의 n이라면 앞의 두 값을 더한 것과 같은 값을 갖는다.

이 성질을 이용하면 아주 빠르게 답을 구해낼 수 있다.

조금만 생각해보면 fibonacci(n)을 실행했을 때 (n > 0일 때)

return 0은 fibonacci(n - 1)번, return 1은 fibonacci(n)번 실행되는 것을 알 수 있다.

(n = 0일 때는 각각 1번, 0번이다)

피보니치 수열을 빨리 구하는 방법은 여기를 참고하자.

3. 코드

3-1. 기본적인 생각

#include <iostream>

int a[2] = { 0 };

int fibonacci(int n) {
	if (n == 0) {
		::a[0]++;
		return 0;
	}
	else if (n == 1) {
		::a[1]++;
		return 1;
	}
	else {
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		int m;
		scanf("%d", &m);
		fibonacci(m);

		printf("%d %d\n", ::a[0], ::a[1]);
		::a[0] = 0;
		::a[1] = 0;
	}

	return 0;
}

3-2. 재귀적 성질 이용하기

#include <iostream>

int fibonacci(int n) {
	static int mem[41] = { 0 };
	if (mem[n] > 0) return mem[n];
	if (n == 0) return 0;
	if (n == 1 || n == 2) return 1;
	return mem[n] = fibonacci(n - 2) + fibonacci(n - 1);
}


int main() {
	int T, N;
	scanf("%d", &T);

	for (int i = 0; i < T; ++i) {
		scanf("%d", &N);
		if (N == 0) printf("1 0\n");
		else printf("%d %d\n", fibonacci(N - 1), fibonacci(N));
	}

	return 0;
}