[백준] 2565. 전깃줄(실버1)

백준(실버1) - 2565. 전깃줄(실버1)

풀이

처음에는 어떻게해야 교차하는 전깃줄을 찾아내지?라는 생각을 하고 있었는데 조금만 더 생각해보니 굳이 교차하는 전깃줄을 찾을 필요가 없었다.
역발상으로 전깃줄이 교차되지 않는 가장 긴 경우의 수를 구하고, 전체에서 그 길이를 빼면 교차되는 전깃줄을 구할 수 있다.

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

public class Main {

	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] wire = new int[n][2];
		int[] LIS = new int[n];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			wire[i][0] = Integer.parseInt(st.nextToken());
			wire[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(wire, new Comparator<int[]>() {
		    @Override
		    public int compare(int[] o1, int[] o2) {
		    	return o1[0] - o2[0];
		    }
		});
		int max = 0;
		for(int i=0; i<n; i++) {
			LIS[i] = 1;
			for(int j=0; j<i; j++) {
				if(wire[j][1]<wire[i][1]) {
					LIS[i] = Math.max(LIS[i], LIS[j]+1);
				}
			}
			max = Math.max(max, LIS[i]);
		}
		System.out.println(n-max);
	}

}