[백준] 2565 전깃줄

문제링크: www.acmicpc.net/problem/2565

2565번: 전깃줄

지난번에 이어서 백준 단계별로 풀어보기 다이나미프로그래밍 문제다.

LIS라는 생각이 안떠오르면 어려울 것 같다.

나도 그리디로 접근하다가 생각보다 오래걸렸다. 어려운 구현 문제를 더 많이 풀어봐야겠다고 생각했다.

근데 N이 100이라 비효율적으로 짜더라도 풀릴 것 같긴 하다.

 

import java.io.*;
import java.util.*;
public class Main {
	public static class Node implements Comparable<Node>{
		int x;
		int y;
		@Override
		public int compareTo(Node o) {
			if (x>o.x) return 1;
			else if(x==o.x) return 0;
			return -1;
		}
	}
	public static int N, lis[];
	public static Node []node;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		node = new Node[N+1];
		lis = new int[N+1];
		for(int i=1;i<=N;i++){
			st = new StringTokenizer(br.readLine());
			node[i] = new Node();
			node[i].x = Integer.parseInt(st.nextToken());
			node[i].y = Integer.parseInt(st.nextToken());
		}
		node[0] = new Node();
		node[0].x=-1; node[0].y=-1;
		Arrays.sort(node);
		for(int i=1;i<=N;i++) {
			for(int j=0;j<i;j++) {
				if(node[i].y > node[j].y) {
					lis[i] = Math.max(lis[j]+1, lis[i]);
				}
			}
		}
		int ans = 0;
		for(int i=1;i<=N;i++) {
			ans = Math.max(ans, lis[i]);
		}
		System.out.println(N-ans);
	}
}