백준 9009 피보나치 c++

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

9009번: 피보나치

문제를 보자마자 든 생각

1. 아 피보나치 배열 만들어야겠다

2. 아 input 중 제일 큰 것 까지 만들어야겠다.

3. 아 현재 target보다 작고 제일 큰 피보나치부터 빼면 되겠다.

 

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

using namespace std;
vector<int> fibo, input;

void f(int target) {
	vector<int> res;
	int idx = fibo.size() - 1;
	while (target > 0) {
		while (fibo[idx] > target)
			idx--;
		target -= fibo[idx];
		res.push_back(fibo[idx]);
	}
	for (int i = res.size() - 1; i >= 0; i--)
		cout << res[i] << ' ';
	cout << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int input_n;
		cin >> input_n;
		input.push_back(input_n);
	}

	int maxx = -1;
	for (int i = 0; i < input.size(); i++)
		maxx = max(input[i], maxx);

	fibo.push_back(0);
	fibo.push_back(1);
	for (int i = 2; fibo[i - 1] + fibo[i - 2] <= maxx; i++)
		fibo.push_back(fibo[i - 1] + fibo[i - 2]);

	for (int i = 0; i < input.size(); i++)
		f(input[i]);
}

그러하다.

98프로에서 터졌다. 백준 특 98프로에서 터지면 0, 1 이런거임 역시나 한자리 숫자일때 문제였다.