[Java] 백준 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 보다 같거나 작은 양의 정수이다.

출력

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

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

예제 입력 1

100

예제 출력 1

8
100 62 38 24 14 10 4 6

 

소스코드

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

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N;
	private static List<Integer> list;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(bf.readLine());
		list=new ArrayList<>();
		
		int result=0;
		for(int i=N;i>=N/2;i--) {
			List<Integer> tmp=new ArrayList<>();
			int first=N;
			int second=i;
			int tmpNum=i;
			int cnt=1;
			tmp.add(first);
			tmp.add(second);
			
			while(first-second>=0) {
				tmp.add(first-second);
				second=first-second;
				first=tmpNum;
				tmpNum=second;
			}
			
			if(tmp.size()>result) {
				result=tmp.size();
				list=tmp;
			}
		}
		
		System.out.println(result);
		for(int r:list) System.out.print(r+" ");
	}

}

첫번째-두번째=세번째

주어진 수 N에 대하여 두번째로 N/2보다 작은 수가 나올 경우, 세번째 수가 두번째 수보다 작아집니다. 그리고 이 경우에 네번째 수는 음수가 나오게 되므로, 두번째 수는 N/2 이상이 되어야 합니다. 따라서 N부터 N/2까지의 수들을 두번째 수로 규칙을 따라갔을 경우 결과를 구하고, 그 중 최댓값을 찾아주었습니다.