백준 2565번: 전깃줄

문제 설명

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

접근법

• 제거해야 하는 전깃줄의 개수를 직접 구하는것보다 제거하지 않아도 되는 전깃줄의 개수를 구해야 하는 문제입니다.
  • 제거해야 하는 전깃줄 = 전체 전깃줄 - 제거하지 않아도 되는 전깃줄
• 한쪽을 기준으로 순서대로 전깃줄을 정렬했을 때 나머지 부분의가장 긴 증가하는 부분수열만큼 전깃줄을 제거하지 않아도 됩니다.

정답

import java.util.*;
import java.io.*;

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[][] lines = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			lines[i][0] = Integer.parseInt(st.nextToken());
			lines[i][1] = Integer.parseInt(st.nextToken());			
		}
        // 정렬
		Arrays.sort(lines,new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
        
		int[] dp = new int[N];
		Arrays.fill(dp, 1); // 최악의 경우라도 자기자신은 LIS에 포함되므로 최솟값은 1
		for (int i = 1; i < N; i++) { // i번째 값
			for (int j = 0; j < i; j++) { // i이전의 값들
				if(lines[j][1] < lines[i][1]) { // 내 앞의 값이 나보다 작으면
					dp[i] = Math.max(dp[j]+1, dp[i]);
				}
			}		
		} 
        // dp[N-1]이 반드시 LIS의 최댓값이라는 보장은 없음
		int maxVal = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			maxVal = Math.max(maxVal, dp[i]);
		}
		System.out.println(N-maxVal);
	}
	
}