[BOJ] 9009번 피보나치

풀이

먼저 피보나치 수열에 해당하는 벡터를 만들어 둔 이후에, 값을 하나씩 빼가며 조건에 맞는지 확인했다.
피보나치 수열에 해당하는 벡터(이하 피보나치 벡터)의 최대 사이즈는 조건에 주어진 n의
크기 (1 <= n <= 1,000,000,000) 를 만족할 만큼 충분한 크기의 숫자를 넣어주었다.
이후 조건문을 이용하여 만약 꺼내고자 하는 값과 현재까지 꺼낸 값의 합이 목표 숫자보다 더 작다면, 숫자를 꺼내서 더해주는 형식으로 코드를 짜 주었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	init();

	vector<int> fiboVector;

	int f[46];
	f[0] = 1;
	f[1] = 2;

	fiboVector.push_back(1);
	fiboVector.push_back(2);

	for (int i = 2; i < 46; i++) {
		f[i] = f[i - 1] + f[i - 2];
		fiboVector.push_back(f[i]);
	}

	sort(fiboVector.begin(), fiboVector.end(), cmp);

	int fibo, sum, temp;
	int n;
	cin >> n;
	vector<int> ans;

	for (int j = 0; j < n; j++) {
		cin >> fibo;
		sum = 0; temp = 0;

		for (int i = 0; i < 45; i++) {
			if (sum + fiboVector[i] <= fibo) {
				ans.push_back(fiboVector[i]);
				sum += fiboVector[i];
			}
		}
		
		for (int k = 0; k < ans.size(); k++) {
			cout << ans[ans.size() - k - 1] << " ";
		}
		cout << endl;

		ans.clear();
	}

	return 0;
}

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