백준 피보나치

문제

내가 생각했을때 문제에서 원하는부분

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다.
입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다.
각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000.

출력은 표준출력을 사용한다.
하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다.
각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다.

내가 이 문제를 보고 생각해본 부분

BufferedReader를 사용하여 입력을 효율적으로 읽는다.
fibonacci 리스트에 0과 1부터 시작하여 1,000,000,000보다 큰 수가 나올 때까지 피보나치 수를 저장한다.
각 테스트 케이스마다 주어진 정수 n을 읽는다.
fibonacci 리스트를 가장 큰 수부터 (10억보다 큰 수는 제외하고) 순회한다.
현재 피보나치 수가 n보다 작거나 같으면, 그 피보나치 수를 result 리스트에 추가하고 n에서 해당 값을 뺀다.
이는 그리디하게 가장 큰 가능한 피보나치 수를 선택하는 과정이다.
모든 피보나치 수를 확인한 후, result 리스트에 저장된 선택된 피보나치 수들을 오름차순으로 정렬한다.
정렬된 결과를 StringBuilder에 추가하여 한 번에 출력한다.

코드로 구현

package baekjoon.baekjoon_28;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 백준 9009번 문제
public class Main1025 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 10억보다 큰 피보나치 수를 미리 계산 (f0=0, f1=1 기준)
        List<Long> fibonacci = new ArrayList<>();
        fibonacci.add(0L); // f0
        fibonacci.add(1L); // f1

        while(fibonacci.get(fibonacci.size() - 1) <= 1_000_000_000L) {
            long nextFib = fibonacci.get(fibonacci.size() - 1) + fibonacci.get(fibonacci.size() - 2);
            fibonacci.add(nextFib);
        }

        // 문제에서 f0=0, f1=1로 시작하지만, 양의 정수를 나타낼 때 0은 사용되지 않으므로 f1=1부터 시작하는 것으로 간주할 수 있습니다.
        // 실제 문제 풀이에서는 0을 제외한 1부터 시작하는 피보나치 수를 사용하는 것이 자연스럽습니다.
        // 여기서 계산된 fibonacci 리스트는 0, 1, 1, 2, 3, 5, ... 형태로 저장됩니다.
        // 1,000,000,000에 대해 가장 큰 피보나치 수를 찾으려면 리스트의 마지막부터 탐색하는 것이 효율적입니다.
        // 리스트에서 0과 첫 번째 1은 제외하고 사용하는 것이 일반적인 문제 해결 방식입니다.
        // 따라서 fibonacci 리스트에서 인덱스 1번(값 1)부터 사용하는 것으로 생각하면 됩니다.
        // 계산된 피보나치 수들: 0, 1, 1, 2, 3, 5, 8, ..., 987, 1597, ..., 754011380, 1213930000+

        int T = Integer.parseInt(br.readLine()); // 테스트 데이터 수

        for(int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine()); // 주어진 정수 n
            List<Long> result = new ArrayList<>(); // 선택된 피보나치 수를 저장할 리스트

            // 계산된 피보나치 수 리스트를 큰 수부터 탐색 (마지막 0이나 첫 번째 1은 건너뛸 수 있음)
            // 10억보다 큰 마지막 피보나치 수를 제외하고 그 이전 인덱스부터 시작합니다.
            for(int i = fibonacci.size() - 1; i >= 1; i--) {
                long currentFib = fibonacci.get(i);
                if(n >= currentFib) {
                    n -= currentFib;
                    result.add(currentFib);
                }
            }

            // 선택된 피보나치 수를 오름차순으로 정렬
            Collections.sort(result);

            // 결과 출력
            for(int i = 0; i < result.size(); i++) {
                sb.append(result.get(i)).append(i == result.size() - 1 ? "" : " ");
            }
            sb.append("\n");
        }

        System.out.print(sb.toString());
        br.close();
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.