백준 9009번 피보나치 C++

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

 

1,000,000,000 까지 포함할 수 있는 피보나치 배열을 만들고, 큰 값부터 빼가면서 답을 구했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	vector<int> fib(47);
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < 47; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}

	while (t--) {
		vector<int> ans;
		int num;
		cin >> num;
		for (int i = 46; i >= 1; i--) {
			if (num < fib[i]) continue;
			ans.push_back(fib[i]);
			num -= fib[i];
		}
		for (int i = ans.size() - 1; i >= 0; i--) {
			cout << ans[i] << " ";
		}
		cout << "\n";
	}
};