[백준/Java] 2565번 전깃줄

-Code

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

public class BOJ2565 {
    static class LineInfo {
        int left, right;

        public LineInfo (int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));

        int cnt = Integer.parseInt(br.readLine());

        LineInfo[] lines = new LineInfo[cnt];
        for (int i = 0; i < cnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            lines[i] = new LineInfo(left, right);
        }
        // 정렬
        Arrays.sort(lines, (o1, o2) -> {
            return o1.left - o2.left;
        });
        // dp
        int maxVal = 0;
        int[] dp = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                // 정렬된 전선의 오른쪽을 기준로 LIS 구하기
                if (lines[i].right > lines[j].right) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxVal = Math.max(maxVal, dp[i]);
        }
        System.out.println(cnt - maxVal);
    }
}

LIS 알고리즘이라고는 하나 2개의 값을 가지고 어떻게 하는지 몰랐습니다. 그래서 좀 찾아보니 둘 중 1개로만 비교하면 되고 시작점을 기준으로 정렬하면 오른쪽에 수가 꼬이는 전선을 쉽게 구할 수 있는 위치로 가게 됩니다. 이후 LIS로 계산하면 꼬이지 않고 연결되는 수가 구해지게 되고 전체 전선수에서 꼬이지 않고 연결되는 수를 빼면 제거해야 하는 전선의 수가 나와서 해결하게 되었습니다.