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

#include <iostream>

using namespace std;

class Fibonacci {
	int a = 0;
	int b = 0;
public:
	Fibonacci() {}
	int fibonacci(int n) {
		if (n == 0) {
			count_a();
			return 0;
		}
		else if (n == 1) {
			count_b();
			return 1;
		}
		else {
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}
	void count_a() {
		a++;
	}
	void count_b() {
		b++;
	}
	int get_a() {
		return a;
	}
	int get_b() {
		return b;
	}
	void reset_a() {
		a = 0;
	}
	void reset_b() {
		b = 0;
	}
	~Fibonacci() {}
};

int main(){
	Fibonacci fi = Fibonacci();
	int n, k;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		fi.fibonacci(k);
		cout << fi.get_a() << " " << fi.get_b() << endl;
		fi.reset_a();
		fi.reset_b();
	}
	return 0;
}

 

다음과 같이 풀고자 했으나 시간 초과가 떴다.

이유를 찾아보니 재귀함수를 사용하여 이미 fibonacci(3)을 구한 적이 있지만 또 다시 구하는 상황이 발생해서이다.

따라서 다이나믹 프로그래밍 기법을 사용했다. 아래와 같다.

 

#include <iostream>

using namespace std;
void fibonacci(int k, int save[40][3])
{
	save[0][0] = 0;
	save[0][1] = 1;
	save[0][2] = 0;
	save[1][0] = 1;
	save[1][1] = 0;
	save[1][2] = 1;
	for (int i = 2; i <= k; i++) {
		save[i][0] = save[i - 1][0] + save[i - 2][0];
		save[i][1] = save[i - 1][1] + save[i - 2][1];
		save[i][2] = save[i - 1][2] + save[i - 2][2];
	}
}
int main(){
	int n, k;
	int save[40][3];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		if (k == 0) {
			cout << 1 << " " << 0 << '\n';
			continue;
		}
		else if (k == 1) {
			cout << 0 << " " << 1 << '\n';
			continue;
		}
		fibonacci(k, save);
		cout << save[k][1] << " " << save[k][2] << '\n';
	}
	return 0;
}

 

 

 

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

1003번: 피보나치 함수