[C++] [실버 1] 9009번: 피보나치

링크

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

9009번: 피보나치

문제

입출력 예제

코드

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

using namespace std;

int main(void)
{
    int pibo[46] = {};

    pibo[0] = 0;
    pibo[1] = 1;

    // 피보나치 배열
    for(int i = 2; i < 46; i++)
    {
        pibo[i] = pibo[i - 1] + pibo[i - 2];
    }

    int num = 0;
    cin >> num;

    for (int i = 0; i < num; i++)
    {
        int testData = 0;
        vector<int> result;

        cin >> testData;
        for (int j = 45; j > 0; j--)
        {
            if (pibo[j] <= testData)
            {
                testData -= pibo[j];
                result.push_back(pibo[j]);
            }
         }

        sort(result.begin(), result.end());
        for (int j = 0; j < result.size(); j++)
        {
            cout << result[j];
            if (j < result.size() - 1)
            {
                cout << " ";
            }
        }
        cout << "\n";
    }

    return 0;
}

풀이

피보나치 Fk 는 (Fk-1 + Fk-2) 로 정의된다.
초기값은 f0 = 0, f1 = 1 이다.

 

반복문을 이용해서 피보나치 배열을 채워주었고,

만약 정수 100을 최소 개수의 피보나치 수들의 합으로  구하려면

89 + 8 + 3 = 100 과 같이

정수보다 작은 수 들 중 가장 큰 수를 더하는 그리디 알고리즘을 사용하는 것이 효율적일 것이다.

 

해당 과정을 반복문을 이용하여 구현해 주고 더할때 사용한 피보나치 수들은 answer라는 이름의 int형 벡터에
저장한다.
이후 해당 벡터를 오름차순으로 출력하기 위해 sort를 이용해 정렬해 주었고
반복문을 이용해 출력해 주었다.