[java 백준] 골드 5/ 2565번 전깃줄

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

2565번: 전깃줄

import java.io.*;
import java.util.*;
 
public class Main {
 
 
    public static int n;
    public static int [][]arr;
    public static int []dp;
 
    public static void main(String[]args) throws IOException {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
 
        arr=new int[n+1][2];
        dp=new int [n+1];
 
        //comparator
 
        for(int i=1;i<=n;i++){
            for(int j=0;j<2;j++){
                arr[i][j]=sc.nextInt();
            }
        }
 
        Arrays.sort(arr,new Comparator<int[]>(){
           @Override
           public int compare(int []a,int []b){
               if(a[0]<b[0]){
                   return -1;
               }else if(a[0]>b[0]){
                   return 1;
               }
               return 0;
           }
 
        });
 
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=1;
            for(int j=1;j<i;j++){
                if(arr[j][1]<arr[i][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
 
            }
        }
 
        int max=0;
        for(int i=1;i<=n;i++){
            if(max<dp[i]){
                max=dp[i];
            }
        }
 
        System.out.println(n-max);
 
 
    }
}
 

 

기를 쓰고 comparator를 쓰지 않고 싶었지만 그렇게 풀지 않으면 틀리는 문제였다.

전깃줄을 제거하는 최솟값은 LIS를 통해 증가하는 수열을 구하고 n에서 최대 증가하는 수열 길이를 빼주면 끝난다! 

 

https://seeminglyjs.tistory.com/208

[Java] Comparator/ compare 에 대하여 알아보자!

comparator에서

 

a[0]이 b[0] 보다 크면 1반환

a[0]이 b[0] 보다 작으면 -1 반환한다 !