[백준알고리즘] 브루트포스 - 2635번 수 이어가기 문제

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

2635번: 수 이어가기

 

주어지는 첫번째 수의 최대 크기가 30000이기 때문에 브루트포스로 다 해봐도 30000을 넘지 않는다

(그 이상의 수까지 볼 필요가 없는게, 우리는 나올수 있는 가장 긴 수를 구해야 하기 때문에 두번째로 올 수가 첫번째로 오는 수보다 더 클 필요가 없다..그러면 바로 처음부터 음수값이 나올것이기 때문에)

두번째로 올 수를 0부터 첫번째로 오는 수(N이라고 하겠음)까지 봐가면서

(이때 내가 비교문을 잘못해놔서 첨에 틀렸습니다 떴었다..

i<N으로 하지말고 <=로 해서 꼭 i가 N까지 오도록 해야한다. 예시: 1 1 0 1)

max값을 구하고 그 수들을 ArrayList에 넣는 식으로 했다.

단순하게 풀려서 크게 할 말은 없다..

다른 코드도 봐봐야겠다..

 

* al에 있는 원소들을 maxAl에 담는 과정을 maxAl.addAll(al);로 편하게 할 수 있다.

package baekjoonWeek4;

import java.io.*;
import java.util.ArrayList;

public class BJ_2635 {  //수 이어가기 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    //첫번째로 주어질 수
        ArrayList<Integer> al = new ArrayList<>(N);
        ArrayList<Integer> maxAl = new ArrayList<>(N);  //최대 길이가 되는 값들을 저장할 리스트

        int pre;    //연산할때 앞에있는 수
        int next;   //연산할때 뒤에있는 수
        int max = 0;    //최대길이값
        int temp = 0;
        int tmp;
        for (int i = 0; i <= N; i++) {   //여기서 <N이라고 한게 문제였다. N을 포함해야함
            al.clear();
            al.add(N);
            al.add(i);
            pre = N;
            next = i;
            while (pre - next >= 0) { //다음에 오는 수가 음수가 되면 끝
                al.add(pre - next);
                tmp = next;
                next = pre - next;
                pre = tmp;
            }
            if (al.size() > max) {  //리스트 크기가 Max값보다 크다면(더 길다면)
                maxAl.clear();  //비워주자
                max = al.size();
                while (!al.isEmpty()) {     //이거보다 더 좋은 옮기는 방법 없을까??
                    maxAl.add(al.remove(0));
                }
            }

        }
        temp = 0;
        bw.write(Integer.toString(max));
        bw.newLine();
        while (!maxAl.isEmpty()) {
            bw.write(maxAl.remove(0) + " ");
        }
        bw.flush();
        bw.close();
    }


}