전깃줄 2565

https://www.acmicpc.net/problem/2565

처음에는 단순히 가장 많이 교차하는 전선을 찾아서 하나씩 순차적으로 제거하면서 교차여부를 판정하면 안될까 싶었지만 안된다

이문제는 DP인데 DP로 풀 수 있는지조차 몰랐다
그리고 이문제는 가장긴증가하는부분수열을 찾는 문제이고 찾는 방법이 DP이다

A를 기준으로 정렬을 하고
A의 인덱스를 활용해서 이중FOR문 돌리면서
0,1
0,2 1,2
0,3 1,3 2,3
0,4 1,4 2,4 3,4

이런식으로 비교하면서 왼쪽 인덱스A(더작은수)의 값(B)이 오른쪽A의 값(B) 보다 작으면 DP[A] 배열에 값을 넣는다. DP배열은 1로 초기화된 상태에서 사용해야 한다. 이런식으로 가장긴증가하는부분수열의 크기를 구한다.... 그리고 (전체 전선의 개수) - (가장긴증가하는부분수열의 크기) = 답

위의 그림처럼 DP배열에 1,1,2,1,2,3,4,5 이렇게 숫자가 세팅된다

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

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

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

    @Override
    public int compareTo(Line o){
        return this.a < o.a ? -1 : 1;
    }
}
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        String[] input;

        Line[] lines = new Line[n];

        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");

            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

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

        Arrays.sort(lines);

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

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

        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }

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