백준 BOJ 9009 - 피보나치

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

9009번: 피보나치

그리디 알고리즘을 사용한다.

문제 지문을 관찰해보면

양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실

이라는 언급이 있다.

이를 통해서 유추해 볼 수 있는 사실으로,

어떠한 수 K에서 피보나치 수 F를 빼서 k를 만들면,

그 새로운 수 k도 다시 피보나치 수들의 합으로 나타낼 수 있다는 것을 알 수 있다.

 

어떠한 수를 피보나치 수 F들의 합으로 구성한다고 할 때,

두 피보나치 수 $F_i$ 와 $F_{i+1}$ 이 합을 구성하는데 필요하다고 한다면

피보나치 수의 정의에 따라 $F_{i+2}$ 를 대신 더해주는게

보다 적은 갯수로 합을 구성할 수 있게 된다.

 

따라서 만일 $F_{i+2}$를 선택할 수 있는 상황이라면

$F_i$ 와 $F_{i+1}$를 선택하는것보다 $F_{i+2}$를 선택하는게 이득이 된다.

이는 모든 i에 대해서 적용 가능하기 때문에,

 

최종적으로 N보다 작거나 같으면서 가장 가까운 피보나치 수 F를 찾아서

지속적으로 빼주면서 N을 관리해주면 된다.

 

피보나치 수들을 반복문을 통해서 만들어주고,

피보나치 수 F를 찾는데는 이분탐색을 이용했다.

upper_bound는 자기 자신보다 큰 원소의 위치를 반환하니

upper_bound로 찾아낸 위치에서 1을 제외해주면

작거나 같으면서 가장 큰 수 F를 쉽게 찾을 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> fibo;

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int tmp = 0;
	fibo.push_back(1);
	fibo.push_back(2);
	while(fibo.back() < 1000000000){
		tmp = fibo.size();
		fibo.push_back(fibo[tmp-1] + fibo[tmp-2]);
	}
	
	int Q;
	cin >> Q;
	while(Q--){
		stack<int> ans;
		int N;
		
		cin >> N;
		
		while(N){
			int idx = upper_bound(fibo.begin(), fibo.end(), N)-fibo.begin();
			N -= fibo[idx-1];
			ans.push(fibo[idx-1]);
		}
		
		while(!ans.empty()){
			int now = ans.top();
			ans.pop();
			cout << now << " ";
		}
		cout << "\n";
	}
}