[BAEKJOON 백준] 2635 수 이어가기

www.acmicpc.net/problem/2635

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

출력

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

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

 

이 문제를 BFS를 이용해서 문제를 풀었다.

먼저 임시로 계속 탐색할 리스트를 만들어 주고, 거기에 모든 수를 넣어주면서 수가 많을때를 찾아 넣어주는 방식이다.

 

두번째수는 무조건 첫번째수의 반보다는 커야한다. 그 보다 작을 경우 무조건 네번째에서 음수가 나오기 때문이다.

 

그래서 입력값의 반부터 시작을 해서 모든 수를 탐색해 준다.

 

그렇게 탐색을 하면서 최소 크기보다 커질때마다 결과 리스트에 넣어주고, 그렇게 탐색이 끝이 나면 결과 리스트를 출력해 준다.

 

 

 

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int max = 0;
		LinkedList<Integer> result=new LinkedList<Integer>();
		for (int i = N/2; i <= N; i++) {
			LinkedList<Integer> arrlist = new LinkedList<Integer>();
			arrlist.add(N);
			int temp = N;
			int temp2=i;
			while (true) {
				arrlist.add(temp2);
				int t=temp;
				temp=temp2;
				temp2=t-temp;
				if (temp2 < 0) {

					temp = arrlist.size();

					break;
				}
			}
			if (temp > max) {
				result=arrlist;
				max = temp;
			}
		}
		System.out.println(max);
		for (int i = 0; i < max; i++) {
			System.out.print(result.poll()+ " ");
		}
	}
}