[BJ] 백준 2635 수 이어가기 (JAVA)

문제

https://www.acmicpc.net/problem/2635

 

풀이 방법

첫 번째 수를 입력으로 받고 두번째 수를 선택한 뒤 세번째 부터는 앞에 두 개의 숫자를 빼면서 하나씩 새로운 수를 만들어가는 문제이다. 
1. N 부터 1 까지 하나씩 두번째 수로 선택 한다.
2. 음수가 나올때까지 while문에서 세번째 수 부터 하나씩 만들면서 list에 추가한다.
3. 하나의 list가 만들어질 때마다 최대 크기를 비교해서 업데이트하고, 업데이트가 되는 경우엔 배열도 같이 복사해준다.
3. 마지막엔 최종적으로 max에 담겨있는 개수와 list를 출력해줬다.

 

제출 코드

import java.io.*;
import java.util.*;
public class BJ_2635_수이어가기 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());

    List<Integer> list = new ArrayList<>();
    List<Integer> copy = new ArrayList<>();

    int max = 0;
    for (int i = N; i >= 1; i--) { //N부터 1까지 하나씩 두번째 수로 선택하기
      list.add(N);
      list.add(i);
      while (true) {
        int n = list.get(list.size() - 2) - list.get(list.size() - 1); //i-1 - i-2를 구해서 음수인지 체크
        if (n < 0) break; 
        else list.add(n);
      }
      if (max < list.size()) { //최대 크기 업데이트
        max = list.size();
        copy.clear();
        copy.addAll(list); //최대 크기이면 배열 복사
      }
      list.clear(); //매번 초기화 해주기
    }
    sb.append(max);
    sb.append("\n");
    for (Integer i : copy) {
      sb.append(i);
      sb.append(" ");
    }
    sb.setLength(sb.length() - 1);
    System.out.println(sb);
  }
}