백준|9009번|피보나치

문제설명
어느 한 정수를 입력받고 피보나치 수들의 합으로 나타내려고 할 때 최소한의 개수의 피보나치 수로 나타내는 방법을 출력하는 문제입니다.

작동 순서
1. 연산횟수 N을 입력받습니다.
2. 입력 값이 10억 까지이므로 피보나치 수열을 45번째 까지만 구해줍니다.(45번째 피보나치 수는 10억을 초과합니다.)
3. 정수 num을 입력받습니다.
4. 피보나치 수열의 뒤쪽부터 num보다 작은 값을 스택에 넣어주고 그 값만큼 num을 감소시킵니다.
5. num이 0이되면 연산을 끝내고 스택에 저장되있던 값을 작은 수부터 StringBuilder에 넣어줍니다.(뒤에서 부터 계산을 해서 스택에는 큰 숫자가 먼저 들어갔기 때문에 꺼낼 때는 작은 수부터 꺼냅니다.)
6. 모든 연산이 끝나면 StringBuilder에 저장되어 있는 값들을 출력합니다.

소스코드

import java.io.*;
import java.util.Stack;
public class 백준_9009번_피보나치 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb  = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int T = Integer.parseInt(br.readLine());

        int[] fibo = new int[46];
        fibo[1]=1;
        fibo[2]=1;

        for(int i=3;i<46;i++) fibo[i]=fibo[i-1]+fibo[i-2];

        for(int i=0;i<T;i++){
            int num = Integer.parseInt(br.readLine());
            for(int j=45;j>0;j--){
                if(fibo[j]<=num) {
                    num-=fibo[j];
                    stack.add(fibo[j]);
                    if(num==0) break;
                }
            }
            while(!stack.empty()) sb.append(stack.pop()).append(" ");
            if(i<T-1) sb.append("\n");
        }
        System.out.print(sb);
    }
}