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

 

문제

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

9009번: 피보나치

 

 

사용한 알고리즘

• 2022.01.11 - [PS/Algorithm] - [알고리즘 개념정리] 1. 정렬 (sort STL), 특정 변수 기준으로 정렬하기

-> 내림차순 정렬. 방법2

• 2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디

 

 

풀이

1. 벡터 v에 피보나치 수들을 미리 오름차순으로 push해준다.
2. 테스트 케이스마다 정수 x를 입력받는다.
3. 피보나치 수가 들어있는 벡터v를 거꾸로 (큰 수 부터) 순회한다.
   이 때 sum+피보나치 수 <= x 이면
   피보나치 수를 sum에 더해주고 ans 벡터에도 push해준다.
4. sum이 x와 같아지면 break하고 ans벡터를 오름차순 출력한다.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // 1. 벡터 v에 피보나치 수들을 미리 오름차순으로 push해준다.
    vector<int> v;
    v.push_back(0);
    v.push_back(1);
    while(1){
        int tmp=v[v.size()-1]+v[v.size()-2];
        if(tmp>1000000000) break;
        v.push_back(tmp);
    }

    int len=v.size();
    int tc; cin>>tc;
    for(int i=0; i<tc; i++){
        // 2. 테스트 케이스마다 정수 x를 입력받는다.
        int x; cin>>x;
        vector<int> ans;
        int sum=0;

        /*
         3. 피보나치 수가 들어있는 벡터v를 거꾸로 (큰 수 부터) 순회한다.
            이 때 sum+피보나치 수 <= x 이면
            피보나치 수를 sum에 더해주고 ans 벡터에도 push해준다.
        */
        for(int j=len-1; j>=0; j--){
            if(sum+v[j]<=x){
                sum+=v[j];
                ans.push_back(v[j]);
            }
            // 4. sum이 x와 같아지면 break하고 
            if(sum==x) break;
        }
        // 4. ans벡터를 오름차순 출력한다.
        reverse(ans.begin(),ans.end());
        for(auto &k:ans) cout<<k<<" ";
        cout<<'\n';
    }


    return 0;
}