/ BOJ

BOJ_2635_수이어가기_JAVA

문제 : 수이어가기

링크 : BOJ_2635_수이어가기

접근 방식

리스트를 이용한다. 특정 수가 주어지면, 0부터 시작해서 반복하는데, 내부반복분으로 끝에서부터 2번째와 첫번째의 차를 리스트에 계속해서 추가하는 방법으로 문제를 풀어나간다.

매 번 추가하고 나서, 해당 하는 리스트의 끝 값이 만약 음수라면 해당하는 값을 빼고 반복을 종료한다. 내부반복이 종료되면 리스트의 길이가 최대인지 확인하고, 만약 최대하면 리스트의 길이와 해당 최대 리스트를 저장한다.

풀이 방법

  1. 주어진 값을 읽어와서 N에 저장하고 i는 0부터 N까지 반복한다.

  2. 리스트를 생성한다. N값을 첫번째, i값을 2번째 값으로 추가한다.

  3. 내부에서 while 반복문을 돌린다.

  4. 리스트 끝에서부터 2번째 - 끝에서부터 1번째 값을 구해서 리스트에 추가한다.

  5. 만약 추가한 값이 음수라면 리스트에서 제거하고 반복문을 나간다.

  6. while문이 끝나면 리스트의 길이를 비교한다.

  7. 만약 리스트의 길이가 최대라면, 해당 리스트의 길이와 리스트를 저장한다.

  8. 모든 반복이 종료된 후 저장된 리스트의 길이 리스트 목록을 출력한다.

소스 코드


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

public class BOJ_2635_수이어가기 {

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

		int N = in.nextInt();

		int max = 0;
		List<Integer> anslist = null;
		for(int i=0;i<=N;i++) {
			List<Integer> list = new ArrayList<>();
			list.add(N);
			list.add(i);
			while(true) {
				list.add(list.get(list.size()-2) - list.get(list.size()-1));

				if(list.get(list.size()-1) < 0) {
					list.remove(list.size()-1);
					break;
				}
			}
			if(max < list.size()) {
				max = list.size();
				anslist = list;
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(anslist.size()).append("\n");
		for(int i=0;i<anslist.size();i++) {
			sb.append(anslist.get(i)).append(" ");
		}
		System.out.println(sb);

	}
}