백준 2565번 - 전깃줄

문제

백준 2565번 - 전깃줄

아이디어

• 없애야 하는 전깃줄의 수는 전체 전깃줄 - 제거하고 남은 전깃줄의 개수와 같다.
• 그럼 제거하고 남은 전깃줄을 어떻게 구해야 할까?
• 전깃줄이 서로 교차하지 않기 위해서는 전깃줄이 서로 크로스 되지 않고, 연속적으로 위치해 있어야 한다.
• 즉, 전깃줄이 연결되어 있는 정보를 정렬하여 B 전봇대에서 가장 긴 증가하는 부분 수열의 길이가 제거하고 남은 전깃줄의 개수가 된다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

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

public class BJ_2565 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine()); //전체 전깃줄의 개수

        Line[] lines = new Line[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            lines[i] = new Line(a, b);
        }

        Arrays.sort(lines);

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int max = 1;

        //가장 긴 증가하는 부분 수열의 길이 구하기
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (lines[i].b > lines[j].b && dp[i] + 1 == dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println(n - max);
    }

    static class Line implements Comparable<Line> {
        int a, b;

        public Line(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public int compareTo(Line o) {
            if (this.a == o.a) {
                return this.b - o.b;
            }
            return this.a - o.a;
        }
    }
}