[백준] 2565 전깃줄

문제 출처: www.acmicpc.net/problem/2565

2565번: 전깃줄

: 전깃줄을 몇 개 잘라서 교차하는 전깃줄을 없애려고 한다.

: 이때 잘라야 하는 전깃줄의 최소 개수를 구해야 한다.

: A쪽의 번호를 인덱스로 B쪽의 번호를 값으로 하는 배열의 최장 증가 부분수열을 구해야하는 것을 알 수 있다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[] list = new int[501];
		int[] LIS = new int[501];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			list[idx] = value;
		}
//		System.out.println(Arrays.toString(list));
		int size = 0;
		for(int i = 0; i < 501; i++) {
			if(list[i] == 0) continue;
			int idx = Arrays.binarySearch(LIS, 0, size, list[i]);
//			System.out.println(idx);
			idx = Math.abs(idx) - 1;
			LIS[idx] = list[i];
			if(size == idx) ++size;
		}
//		System.out.println(Arrays.toString(LIS));
		System.out.println(N-size);
	}
}