[BOJ] 9009번_피보나치_그리디_C++

[문제]

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

피보나치 수 fk는 fk=fk-1+fk-2로 정의되며 초기값은 f0=0과 f1=1이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다.

하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 f4+f6+f9+f10 = 3+8+34+55등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타고 출력하는 것이다.

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하는 문제이다.

[사용 알고리즘]

그리디

[풀이 핵심]

• 먼저 피보나치수로 이루어진 배열을 만들어준다. n의 값이 최대 1,000,000,000이므로, 45까지만 만들면된다. (fib[45] = 1,134,903,170)
• 그리디한 방법으로 구해야되는 값보다 작은 수 중 가장 큰 피보나치 수 부터 하나씩 뽑아주면 답이된다. 그리고 현재고른 수 + 지금 고를 수가 최종적으로 구할 값을 넘으면 안된다는 것을 주의해서 조건문을 만들면된다.
• 마지막엔 증가하는 순서로 출력한다는 조건을 맞추기 위해 오름차순 정렬을 해주고 출력하면된다.

[코드]

//boj9009번_피보나치_그리디 알고리즘

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

using namespace std;

int fib[46];

int main() {
	fib[0] = 0;
	fib[1] = 1;

	for (int i = 2; i < 46; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}

	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int n;
		cin >> n;

		int sum = 0;

		vector<int> result;

		for (int j = 45; j >= 0; j--) {
			if (n == sum) {
				break;
			}

			if (sum + fib[j] <= n) {
				sum += fib[j];
				result.push_back(fib[j]);
			}
		}

		sort(result.begin(), result.end());

		for (int k = 0; k <result.size(); k++) {
			cout << result[k] << " ";
		}
		cout << '\n';
	}

	return 0;
}