문제

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하는 문제이다.
가령, 정수 100이 주어지면 100 = ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 = ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89 = ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있지만, 가능한 경우의 수 중 최소 개수인 3 8 89를 출력하면 된다.

입력

첫째줄 : T (테스트 데이터의 수)
둘째줄부터 : n (각 테스트 데이터, 1 ≤ n ≤ 1,000,000,000)

출력

하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다. 이때, 피보나치 수들을 오름순으로 출력한다.

문제풀이

그리디 알고리즘으로 풀면 된다. 해를 구하는 매 단계에서 식을 성립시키는 가장 큰 피보나치 수를 구하면 된다.

코드

import java.io.*;
import java.util.ArrayList;
import static java.util.Collections.sort;

public class Main {
    static ArrayList<Integer> Fibonacci = new ArrayList<>();    //모든 피보나치 수들을 저장한 ArrayList
    static ArrayList<Integer> Combinations = new ArrayList<>();     //해를 저장하기 위한 ArrayList

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        //input
        int t = Integer.parseInt(in.readLine());    //t = 테스트 데이터의 수
        int[] testData = new int[t];   //testData = 테스트 데이터를 저장한 배열
        for (int i = 0; i < t; i++) {
            testData[i] = Integer.parseInt(in.readLine());
        }

        //범위 내 모든 피보나치 수를 구한다.
        CalFibonacciUnder(1000000000);

        //해 구하기
        for (int i = 0; i < t; i++) {   //매 테스트케이스마다
            int num = testData[i];  //num = 주어진 양수(테스트 데이터)

            for (int j = Fibonacci.size() - 1; j >= 0; j--) {
                if (num >= Fibonacci.get(j)) {  //num보다 작은 피보나치 수 중 가장 큰 수
                    Combinations.add(Fibonacci.get(j)); //해에 추가
                    num -= Fibonacci.get(j);    //해에 추가된 값을 뺴기
                }
            }

            sort(Combinations);     //오름름으로 정렬

            //output
            for (Integer combination : Combinations) {
                out.write(combination + " ");
            }
            out.write("\n");
            
            Combinations.clear();   //다음 테스트케이스의 해를 위해 비우기
        }

        out.flush();
    }


    static void CalFibonacciUnder(int n){   //n 이하이의 모든 피보나치 수를 구하여 Fibonacci에 저장하는 함수
        int totalNum = 3, currentNum = 2, nextNum;
        Fibonacci.add(1); Fibonacci.add(1); Fibonacci.add(2);

        while(currentNum <= n){
            nextNum = Fibonacci.get(totalNum - 1) + Fibonacci.get(totalNum - 2);
            if (nextNum < n) {
                Fibonacci.add(nextNum);
                currentNum = nextNum;
                totalNum++;
            }
            else return;
        }
    }
}