[백준 2565번] 전깃줄

문제 링크: 2565번 제목

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

 

먼저 입력을 받은 후 A의 위치에 따라 정렬한다. 정렬된 상황에서 B 전깃줄은 증가하는 수열이어야 하기에 LIS의 최대 길이를 구하고, 이를 전체 전깃줄의 개수에서 빼준다.

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        /* input */
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        if (n==1) {
            System.out.println(0);
            System.exit(0);
        }

        int[][] arr = new int[n][2]; // [i][0]: A, [i][1]: B
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        Arrays.sort(arr, Comparator.comparing(elem -> elem[0]));

        sc.close();

        /* logic */
        dp[0] = 1;
        for (int i = 1; i <= n-1; i++) {
            for (int j = 0; j < i; j++)
                if (arr[j][1] < arr[i][1] && dp[j] >= dp[i])
                    dp[i] = dp[j] + 1;
            if (dp[i] == 0) dp[i] = 1;
        }

        Arrays.sort(dp);
        int max = dp[dp.length-1];

        int answer = n - max;
        System.out.println(answer);
    }
}