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

문제링크 : https://www.acmicpc.net/problem/9009

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

const int MOD = 1000000007;

int arr[45];

int main() {
    int T;
    cin >> T;

    arr[0]=0;
    arr[1]=1;
    for(int i=2; i<45; i++) arr[i] = arr[i-1] + arr[i-2];

    while(T--)
    {
        int n;
        cin >> n;
        vector<int>v;
        for(int i=44; i>=1; i--)
        {
            if(n < arr[i]) continue;
            n -= arr[i];
            v.push_back(arr[i]);
        }
        reverse(v.begin(), v.end());
        for(auto i : v) cout << i << " ";
        cout << "\n";
    }

    return 0;
}

 

우선 피보나치 배열의 값을 채워준다.

문제의 조건에 따라 n의 범위가 1,000,000,000까지 가능하므로, 44까지만 값을 채워준다. (45 : 1,134,903,170)

 

이후로는 뒤에서부터 체크하며 입력받은 n에 대해 arr[i] 값을 감소시켜준다.

이는 그리디하게 가장 큰 값부터 제거하며 최소 개수로 합을 나타내기 위함이다.

이때 조건에 맞는 값들을 따로 벡터에 담아내어 출력해준다.

출력할 때는 담았을 때는 큰 값부터 담았기에 뒤집어서 다시 작은 값부터 출력하도록 해주어야한다.