[백준] 2565 전깃줄 (JAVA)

풀이

이 문제는 가만히 생각하다 보니 복잡하지만 풀이가 보였다. 풀이 방법은 일단 문제에서 주어진 입력값을 전부 받고 그다음 가장 많이 겹치는 순으로 선을 제거해 겹쳐저있는 선들의 수를 계산 해나갔다. 그러나 이 방식으로 하면 시간도 오래걸리고 결론적으로 문제에서 틀렸다고 나오기도 하였다. (배열범위를 벗어났다고 나오지만...) 그래서 구글링을 하였고 역시 내가 생각한 풀이 방법보다 훨씬 깔끔했다. 나는 처음에는 문제에서 하라는대로 전선을 전부 이은후 하나씩 제거 해나갔는데 다른 사람들의 코드는 전부 연결한후 LIS방식으로 지우는 것이 아닌 최대 몇개까지 이을수있는것인가.를 구하고 전체에서 방금 구한수를 빼서 정답을 도출했다. 즉 전체집합에서 여집합을 빼서 구했다. 앞으로는 조금 유연하게 보도록 노력해야겠다.

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

class Main{

    public static void main(String[] args)throws IOException {
        int [][]cost;
        int [] dp;
        int n;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");

        n= Integer.parseInt(st.nextToken());
        cost = new int[n+1][2];
        dp = new int[n+1];

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

        Arrays.sort(cost, 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;
                else
                    return 0;
            }
        });

        dp[1] = 1;

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

        int max = Integer.MIN_VALUE;
        for(int i=1; i<=n; i++){
            if(dp[i]>max)
                max = dp[i];
        }
        System.out.println(n-max);
    }
}