백준 2565 전깃줄(Gold 5)

전략

• 다이나믹프로그램은 항상 식으로 바꿔서 풀자
• 그림에서 규칙 찾아내기
• 왼쪽 전봇대를 기준으로 정렬한 결과 전깃줄이 일관성있게 우하향하거나 우상향 하는 경우만 안 겹친다
• 앞에서 계속 하던 LIS(Longest Increase Sequence)문제와 동일하다!
• 따라서 첫번째 전깃줄을 기준으로 먼저 정렬하고 여기서 최장 증가 수열의 길이를 구하면 되는 문제

정답코드

import java.util.Arrays;
import java.util.Scanner;

class point implements Comparable<point>{
	
	int a;
	int b;
	
	public point(int x, int y) {
		a = x;
		b = y;
	}

	@Override
	public int compareTo(point o) {
		
		if(o.a == this.a) {
			return this.b - o.b; 
		}
		
		return this.a - o.a;
	}	
	
}


public class ElectricWire {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int result = 1;
		point [] elecwire = new point[N];
		int [] DP = new int[N+1];
		Arrays.fill(DP,1);
		
		
		for(int i = 0; i < N; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			point p = new point(x,y);
			elecwire[i] = p;
		}
		
		Arrays.sort(elecwire);
		
		int [] Seq = new int[N]; 
		
		for(int i = 0; i <N; i++) {
			Seq[i] = elecwire[i].b;
		}
		
		for(int i = 1; i < N; i++) {
			for(int j = 0; j<i; j++) {
				if(Seq[j]<Seq[i]&&DP[j]>=DP[i]) {
					DP[i] = DP[j]+1;
				}
			}
		}
		
		for(int i = 0; i< N; i++) {
			result = Math.max(result,DP[i]);
		}
		
		System.out.println(N-result);
	}
}