백준 9009. 피보나치

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

9009번: 피보나치

 

1. 정수 n이 포함되는 피보나치 수열을 구한다

 

2. 찾은 피보나치 수열을 역순으로 돌면서 n과 제일 가까우면서 작은수를 구한다.

   n에서 찾은수를 뺀값의 제일 가까우면서 작은수를 구한다. 반복

   

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{

    int tc;
    cin >> tc;

    while(tc--)
    {
        int n;
        cin >> n;

        vector<int> pibo;
        pibo.push_back(0);
        pibo.push_back(1);

        // 피보나치 수열 생성
        int num = 1;
        while(num <= n)
        {
            num = pibo[pibo.size()-2] + pibo[pibo.size()-1];
            pibo.push_back(num);
        }

        // 답 찾음
        vector<int> ans;
        int target = n;
        for(int i = pibo.size()-1; i >= 0; i--)
        {
            if(pibo[i] <= target)
            {
                ans.push_back(pibo[i]);
                target = target - pibo[i];
            }

            if(target == 0)
                break;
        }

        sort(ans.begin(), ans.end());
        for(auto x : ans)
            cout << x << ' ';
        cout << '\n';
    }



}