[백준] 2635번: 수 이어가기_java

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이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

📎입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

📎출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

📎코드

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		sc.close();

		List<Integer> arr = new ArrayList<Integer>();
		List<Integer> answer = new ArrayList<Integer>();


		int k = 0;
		int MAX_cnt = 0;
		for (int i = N / 2; i <= N; i++) {
			int index = 0;
			arr.add(N);
			arr.add(i);
			
			while (true) {
				k = arr.get(index) - arr.get(index + 1);
				if (k < 0)
					break;
				else {
					arr.add(k);
					index++;
				}
			}
			if(arr.size()>MAX_cnt) {
				answer.clear();
				MAX_cnt=arr.size();
				answer.addAll(arr);
			}
			
			arr.clear();
			
		}

		System.out.println(MAX_cnt);
		for (int i = 0; i < answer.size(); i++) {
			System.out.print(answer.get(i) + " ");
		}

	}

}

📎코드 해석

• 두 번째 수가 첫 번째 수의 1/2 보다 작으면 무조건 출력되는 갯수가 3이므로 1/2보다 작은 경우는 제외하였다.