[백준] 2565 - 전깃줄 [JAVA]

 

 

코드

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

public class Main {

    static int[] dp;
    static int[][] arr;

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

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

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

        arr = new int[N][2];
        dp = new int[N];

        StringTokenizer st;

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

            arr[i][0] = Integer.parseInt(st.nextToken()); // A 전봇대
            arr[i][1] = Integer.parseInt(st.nextToken()); // B 전봇대
        }

        // A 전봇대 기준 오름차순 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        // Bottom-up (LIS)
        for (int i = 0; i < N; i++) {

            dp[i] = 1;

            for (int j = 0; j < i; j++) {
                if (arr[i][1] > arr[j][1] && dp[i] < dp[j] + 1) {
                    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);
    }


}