백준 9009번[c/c++] : 피보나치

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

9009번: 피보나치

---

풀이

재귀적 풀이

• fibo함수에 입력한 값을 넘겨준다
• 넘어온 값이 1이라면 계산할 필요없가 없으므로 1을 출력한다
• 만약 입력한 값이 피보나치 수라면 입력한 값을 그대로 출력한다.
• 입력한 값이 피보나치 수가 아니라면 입력한 값보다 작은 피보나치 수를 구한다(입력한 수보다는 작지만 피보나치 수열중에서는 가장 큰 값) = max_fibo에서 return 해준다. 이 값을 max라고하자.
• 입력한 값-max가 0보다 크다면 아직 남은 숫자들이 있기 때문에 재귀적으로 함수를 호출해주면 가장 작은값 부터 출력이 된다.

#include<stdio.h>
int max_fibo(int n) {
	int i;
	int f0 = 0;
	int f1 = 1;
	int f2;
	if (n <= 1)
		return n;
	while (1) {
		f2 = f1 + f0;
		if (f2 == n)
			return f2;
		else if (f2 > n)
			return f1;
		f0 = f1;
		f1 = f2;
	}
}

void fibo(int n) {
	int max;
	if (n == 1) {
		printf("1");
		return;
	}
	max = max_fibo(n);
	if ((n - max) > 0) {
		fibo(n - max);
		printf(" ");
	}
	printf("%d", max);
}
int main() {
	int ntest;
	int number;
	scanf("%d", &ntest);
	while (ntest--) {
		scanf("%d", &number);
		fibo(number);
		printf("\n");
	}
}

 

 

c++ 값들을  vector에 넣어서 풀기

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int fibo[46];
	fibo[0] = 0;
	fibo[1] = 1;
	for (int i = 2; i < 46; i++) {
		fibo[i] = fibo[i - 1] + fibo[i - 2];
	}
	int ntest;
	cin >> ntest;
	while (ntest--) {
		int number;
		cin >> number;
		vector<int> answer;
		for (int i = 45; i > 0; i--) {
			if (fibo[i] <= number) {
				number -= fibo[i];
				answer.push_back(fibo[i]);
			}
		}
		for (int i = answer.size() - 1; i >= 0; i--) {
			cout << answer[i] << " ";
		}
		cout << "\n";
	}
}

 

 

위에가 vector에 값들을 넣어 vector값들을 출력한 시간 결과이고

아래가 재귀적으로 푼 결과이다

확실히 재귀적으로 푼 풀이가 메모리와 시간을 덜 잡아먹는다.