BOJ_2635 : 수 이어가기

👉 문제링크

2635번: 수 이어가기

---

---

🔸 문제 분석 🔸

• 주어진 자연수를 자연수로 빼며 만든 수열 중 가장 긴 경우의 길이와 그 목록을 출력한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> answer = new ArrayList<>();
        int size = 0;
        for (int i = n; i >= n/2 - 1; i--){
            int deff = n - i;
            ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(n,i));
            size = 2;
            while (deff >= 0){
                arr.add(deff);
                deff = arr.get(++size-2) - arr.get(size-1);
            }
            if (arr.size() > answer.size())
                answer = arr;
        }
        size = answer.size();
        System.out.println(size);
        for (int i = 0; i < size-1; i++)
            System.out.print(answer.get(i) + " ");
        System.out.println(answer.get(size-1));
    }
}

🔸 코드 해석 🔸

• i를 입력받은 n부터 n/2 -1 까지 바꿔가며 수열을 만들어보고 길이를 비교한다.

---

🔸 end 🔸

• 간단한 문제였는데 몇 가지 계산범위를 잘못 생각해서 틀렸습니다가 많이 나왔다.
  • while조건의 deff가 0이 나오면 안되는 줄 알았지만, 음수가 나오지 않는게 조건이었다.
  • deff가 0이 나와도 되므로 i도 n-1이 아니라 n부터 시작해야한다. (n = 1인 경우 오답)
• 혹시 오답에 출력방식이 영향있을까봐 마지막 공백이 없도록 출력도 바꿨지만 영향은 없는 것 같다.