[C++]백준9009번 피보나치

오늘은 백준9009번 피보나치 문제를 풀어보도록 하자.

기초적인 수학적인 지식을 요구하는 문제이다. 어렵지는 않으니 접근법에서 알아봅시다 :)

문제는 다음과 같다.

                               [접근법]

  1. 우선 배열을 만들고 피보나치를 적용하여 10억보다 작은 수 까지만 저장한다. 그 후 idx에 최대 인덱스를 저장 !
  
  2. 예를 들어 100이라는 숫자가 제시되었으면 배열의 맨 끝에서부터 크기를 비교 후, 100보다 작은 값이 나오면 벡터에 넣어줍니다.

  3. 그 후, 100보다 작은 값을 쳐음 만나는 89를 뺀 11로 값을 갱신해주고 위 알고리즘을 반복하면 끝 ! :)

                                     [코드]
#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, idx, num;
	int arr[1001];
	vector<int>v;
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 1;

	cin >> n;

	for (int i = 3;; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
		idx = i;
		if (arr[i] > 1000000000) {
			arr[i] = -1;
			idx -= 1;
			break;
		}
	}

	while (n--) {
		cin >> num;
		for (int i = idx; i >= 1; i--) {
			if (num >= arr[i]) {
				v.push_back(arr[i]);
				num -= arr[i];
			}
		}
		for (int i = v.size() - 1; i >= 0; i--) {
			cout << v[i] << ' ';
		}
		cout << '\n';
		v.clear();
	}
}