[BOJ][Java] Q25543 - X 만들기

 

25543번: X 만들기

---

한참 헤매다가 LIS를 공부한 후 풀어냈다.

LIS 공부한 후에도 시간초과 나서 어떻게 해결할지 좀 헤맴............어렵다......................나는 몽총이.................

 

1.   점을 ArrayList에 저장하고, x좌표를 기준으로 정렬한다.

 

2.  정렬된 list를 가지고 dp를 사용해서 LIS를 구한다.

전체 점을 각각 원점으로 했을 때, 1~4사분면의 LIS 길이를 구한다.

즉, LIS를 구하는 dp 배열 area는 다음과 같이 생겼다.

int[][] area = new int[5][N];

(5인 이유는 편의상 1~4로 사용하려고..!)

 

LIS를 구할 때,

2, 3사분면은 증가하는지 확인해야하고, 1,4사분면은 감소하는지 확인해야 하므로

두개의 for문으로 나누어서 구해주었다.

1, 4사분면에서는 감소하는지 확인하기 위해, 오름차순(x좌표)으로 정렬된 list를 역순으로 검사했다.

 

3. 구해 준 1~4사분면의 LIS를 전부 더해서 가장 큰 경우가 '제일 적은 수의 압정을 제거한 경우' 이다.

 

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

public class Q25543_X만들기 {
    private static class Pos{
        int x, y;
        public Pos(int x , int y ){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Pos> points = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points.add(new Pos(x, y));
        }

        Collections.sort(points, (o1, o2)-> {
            return o1.x - o2.x;
        });



        int[][] area = new int[5][N];

        //각 점을 원점으로 했을 때,
        //2,3사분면의 LIS 구하기
        for (int i = 0; i < N; i++) {
            //원점은 포함하지 않는 LIS 구하기 위해 1이 아닌 0으로 저장(그니까 사실상 할 필요 없음)
//            area[2][i] = 0;
//            area[3][i] = 0;
            for (int j = 0; j < i; j++) {
                Pos posI = points.get(i); //원점
                Pos posJ = points.get(j); //비교할 점
                //j점이 원점 기준으로 2사분면에 있을 경우( x가 더 작고, y가 더 큼)
                if (posI.x > posJ.x && posI.y < posJ.y) {
                    area[2][i] = Math.max(area[2][j] + 1, area[2][i]);
                }
                //j점이 원점 기준으로 3사분면에 있을 경우(x가 더 작고, y가 더 작음)
                else if (posI.x > posJ.x && posI.y > posJ.y) {
                    area[3][i] = Math.max(area[3][j] + 1, area[3][i]);
                }
            }
        }

        //x좌표 정렬 시 감소해야하므로, 뒤에서부터 검사해서 증가하는지 확인하기
        for (int i = N-1; i >= 0; i--) {
//            area[1][i] = 0;
//            area[4][i] = 0;
            for (int j = N-1; j > i; j--) {
                Pos posI = points.get(i);
                Pos posJ = points.get(j);
                //원점 기준으로 1사분면에 있을 경우
                if(posI.x < posJ.x && posI.y < posJ.y){
                    area[1][i] = Math.max(area[1][j] + 1, area[1][i]);
                }
                //원점 기준으로 4사분면에 있을 경우
                else if(posI.x < posJ.x && posI.y > posJ.y){
                    area[4][i] = Math.max(area[4][j] + 1, area[4][i]);
                }
            }
        }

        // 모든 점 기준으로 1,2,3,4 사분면의 LIS 길이의 합이 가장 긴 점을 원점으로 한다.
        int max = 0;
        loop:
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for(int j = 1; j< 5; j++){
                if(area[j][i] < 1){
                    continue loop;
                }
                sum += area[j][i];
            }
            max = Math.max(max, sum);
        }

        if(max == 0){
            System.out.println(-1);
        }else{
            System.out.println(N - max - 1); //1~4사분면의 LIS길이와 원점 빼준다.(제거한 압정의 개수 출력)
        }
    }
}