[BOJ] 2565. 전깃줄

문제 원본 : https://www.acmicpc.net/problem/2565

2565번: 전깃줄

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    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());

        Line[] lines = new Line[n];
        int[] dp = new int[n];

        StringTokenizer st = null;
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            lines[i] = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(lines);

        int max = 0;
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (lines[i].b > lines[j].b) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        bw.write(String.valueOf(n - max));

        bw.close();
        br.close();
    }

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

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

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

• LIS 문제
• A나 B 둘 중 아무거나 기준을 잡고 정렬을 한 뒤 반대편에서 가장 긴 증가하는 부분 수열을 구하면 된다.
• 그 수열의 길이가 전깃줄을 교차하지 않게 만들 수 있는 최대 길이이므로
• 총 전깃줄 수에서 수열의 길이를 빼면 된다.