[Java] 백준 9009 피보나치 - 실버1

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

9009번: 피보나치

 

 

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int testCase = Integer.parseInt(br.readLine());

    List<Integer> fibo = new ArrayList<>();
    fibo.add(0);fibo.add(1);
    fibo.add(1);fibo.add(2);
    fibo.add(3);fibo.add(5);

    for (int tc =0; tc<testCase; tc++) {
      int value = Integer.parseInt(br.readLine());
      List<Integer> result = new ArrayList<>();

      while (value != 0) {
        int idx = 2;
        while (fibo.get(idx) <= value) {
          idx ++;
          if (idx >= fibo.size())
            fibo.add(fibo.get(idx-1) + fibo.get(idx-2));
        }

        result.add(fibo.get(idx-1));
        value = value - fibo.get(idx-1);
      }

      String resultStr = "";
      for (Integer r : result)
        resultStr = ""+ r + " " + resultStr;

      System.out.println(resultStr.strip());
    }
  }
}

• 피보나치 수열 몇 개를 fibo 리스트에 미리 넣어준다
• 값과 가장 가까운 피보나치수열 값을 찾아 result 리스트에 넣는다.
  • fibo리스트에 값이 없으면 while문으로 계속 추가시켜준다
• 가장 가까운 피보나치 수열 값을 뺀 뒤 다시 같은 과정을 반복한다

 

피보나치 수열들의 합으로 항상 결과값이 나오고, 가장 큰 피보나치 수열을 빼면서 구할 수 있기 때문에 그리디한 방법으로 풀 수 있었다