Baekjoon/C++
[백준 1003번] 피보나치 함수
Yo-mi
2023. 7. 21. 02:30
#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;
}