백준 9009: 피보나치 [Java] - 포포

문제

피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다. 

하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 

입력

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

출력

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

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

---

내 제출

public class No9009 {
    static ArrayList<Integer> list;
    static ArrayList<Integer> answer;
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        for (int i = 0; i < num; i++) {
            list = new ArrayList<>();
            answer = new ArrayList<>();

            //한 개의 정수를 입력받는다.
            int n = Integer.parseInt(br.readLine());
            int n1 = 1;
            int n2 = 1;

            while (true) {
                //ArrayList에 피보나치 수열을 담는다.
                //피보나치 수열이 입력받은 정수보다 커지면 break .
                list.add(n1);
                list.add(n2);

                n1 += n2;
                n2 += n1;
                if (n1 > n && n2 > n) break;
            }

            Collections.sort(list, Collections.reverseOrder());
            // 피보나치 수열을 내림차순으로 정렬한다.

            // 입력받은 정수가 0이 될 때 까지 피보나치 수열 중 큰 수부터 차례대로 빼준다.
            // 입력받은 정수보다 큰 수열의 값은 버리고, 빼준 값은 answer에 담은 뒤 출력.
            while (n != 0) {
                for (int k = 0; k < list.size(); k++) {
                    if (list.get(k) <= n) {
                        n -= list.get(k);
                        answer.add(list.get(k));
                    }
                }
            }

            Collections.sort(answer);

            for(int ans : answer){
                System.out.print(ans +" ");
            }
            System.out.println();
        }
    }
}

주석에 간단히 풀이를 달아놓았다.
입력받은 정수(n)에 다다를때까지 피보나치 수열을 구한 뒤 list에 담고, 오름차순 정렬한다.
n이 0이 될 때 까지 list에서 요소를 꺼내서(n보다 큰 요소는 버린다) 빼주고, answer에 담은 뒤 내림차순 정렬
이후 출력한다.