백준 9009 피보나치

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

그리디하게 풀 수 있다는 것만 알면 쉽습니다.

n이하인 가장 큰 피보나치 수를 빼나가면 됩니다.

모든 양의 정수가 서로 다른 피보나치 수들의 합으로 나타낼 수 있다고 알려주었으므로 n이하인 가장 큰 피보나치 수(fibo[x])를 빼지 않는다면 fibo[x-1],fibo[x-2] 2개를 빼야 하므로 손해입니다.

#include<bits/stdc++.h>
using namespace std;
const int INF=1000000000;
vector<int> fibo;
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	fibo.push_back(1);
	fibo.push_back(1);
	int p=1;
	while(fibo[p-1]+fibo[p]<=INF){
		fibo.push_back(fibo[p-1]+fibo[p]);
		p++;
	}
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		stack<int> s;
		for(int i=p;i>=1;i--){
			if(n>=fibo[i]){
				n-=fibo[i];
				s.push(fibo[i]);
			}
			if(n==0) break;
		}
		while(!s.empty()){
			int t=s.top(); s.pop();
			cout<<t<<" ";
		}
		cout<<'\n';
	}
	return 0;
}