백준 - 2635번(수 이어가기)

문제 출처: https://www.acmicpc.net/problem/2635

• 다음과 같은 규칙에 따라 수들을 만들려고 한다.
  1. 첫 번째 수로 양의 정수가 주어진다.
  2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
  3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
  4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.
• 첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.
• 입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> result = new ArrayList<>();
        int N = scanner.nextInt();
        list.add(N);
        int max = 0;

        for (int i = N; i > 0; i--) {
            list.add(i);
            int index = 2;
            while (true) {
                int temp = list.get(index - 2) - list.get(index++ - 1);
                if (temp < 0) break;
                list.add(temp);
            }
            if (list.size() > max) {
                max = list.size();
                result = new ArrayList<>(list);
            }
            list.clear();
            list.add(N);
        }

        sb.append(max).append("\n");
        for (int n : result) {
            sb.append(n + " ");
        }
        System.out.println(sb);
    }

}

• 반신반의하며 푼 풀이가 맞아서 되게 어벙벙했다.
• 정말 단순하게 주어진 수에서 1씩 빼서 1이 될 때까지 반복문을 돌렸다. 시간 초과가 나올 줄 알았으나 통과됐다.
• 모든 경우의 수를 다 시도해서 가장 길이가 많이 나온 경우를 출력하게 했다.
• 다른 최적의 알고리즘이 있는지 체크해 봐야겠다.