[JAVA] 백준 4198. 열차정렬

📌 문제 링크 - https://www.acmicpc.net/problem/4198

 

 

---

 

 

 

 

 

 

문제

에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.

불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.

차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는 것을 거부할 수 있습니다. 에린이 최종적으로 만든 열차는 가능한 길어야(많은 차량으로 구성되어야)하지만, 그 과정에서 열차는 에린이 배열하고자하는 정렬 순서에 맞아야 합니다.

각 차량이 역에 도착하는 순서대로 차량들의 중량이 주어질 때, 에린이 만들 수 있는 가장 긴 열차배열의 길이(=차량의 수)는 얼마입니까?

 

 

 

입력

첫째 줄에 차량의 수를 나타내는 N (0 <= N <= 2000)이 주어집니다. 이후 N개의 각 줄에는 음이 아닌 차량의 무게가 주어집니다. (단, 서로 다른 두 차량의 무게가 같은 일은 발생하지 않습니다.)

 

 

 

출력

에린이 만들 수 있는 가장 긴 열차의 길이를 출력하세요.

 

 

 

 

 

 

---

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/4198
public class Main_4198 {
    private static int N; // 차량의 수
    private static int[] weights; // 차량의 무게


    public static void main(String[] args) throws IOException {
        init();

        int max = getMax();
        System.out.print(max);
    }//main


    private static int getMax() {
        int max = 0;
        int[] lis, lds;
        int lisCnt, ldsCnt;
        int cur;

        for(int i=0; i<N; i++) {
            cur = weights[i]; // 현재 들어오는 차량
            lisCnt = ldsCnt = 1;
            lis = new int[N+1]; // 증가
            lds = new int[N+1]; // 감소

            lis[0] = cur;
            lds[0] = -cur;

            for(int j=i+1; j<N; j++) {
                int weight = weights[j];

                // 현재 차량보다 무거울 경우
                if(weight > cur) {
                    lisCnt = getCnt(weight, lisCnt, lis);
                }
                // 현재 차량보다 가벼울 경우
                else {
                    ldsCnt = getCnt(-weight, ldsCnt, lds);
                }
            }

            // 가장 긴 열차의 길이 갱신
            max = Math.max(max, lisCnt + ldsCnt - 1);
        }

        return max;
    }//getMax


    private static int getCnt(int cur, int cnt, int[] arr) {
        int idx = lowerBound(cur, cnt, arr);
        arr[idx] = cur;

        return idx == cnt ? cnt+1 : cnt;
    }//getCnt


    private static int lowerBound(int target, int end, int[] arr) {
        int start = 0;
        int mid;

        while(start < end) {
            mid = (start + end) / 2;

            if(arr[mid] >= target) end = mid;
            else start = mid + 1;
        }

        return end;
    }//lowerBound


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 차량의 수

        weights = new int[N]; // 차량의 무게

        for(int i=0; i<N; i++) {
            weights[i] = Integer.parseInt(br.readLine());
        }

        br.close();
    }//init


}//class