백준 동적 계획법 - 2565번 : 전깃줄

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

2565번: 전깃줄

---

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		pair[] ab = new pair[n+1];
		pair[] ba = new pair[n+1];
		ab[0] = new pair(0,0);
		ba[0] = new pair(0,0);
		int[] memo = new int[n+1];
		int[] memo2 = new int[n+1];
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());
			ab[i] = new pair(left,right);
			ba[i] = new pair(right,left);
		}
		for(int i=1; i<=n; i++) {
			for(int j=i+1; j<=n; j++) {
				if(ab[i].a>ab[j].a) {
					pair temp = ab[i];
					ab[i] = ab[j];
					ab[j] = temp;
				}
				if(ba[i].a>ba[j].a) {
					pair temp = ba[i];
					ba[i] = ba[j];
					ba[j] = temp;
				}
			}
		}
		int max = -1;
		int max2 = -1;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=i; j++) {
				if(ab[j].b<ab[i].b) {
					memo[i] = Math.max(memo[j]+1, memo[i]);
				}
				if(ba[j].b<ba[i].b) {
					memo2[i] = Math.max(memo2[j]+1, memo[i]);
				}
			}
			if(memo[i]==0) memo[i] = memo[0]+1;
			if(memo2[i]==0) memo2[i] = memo2[0]+1;
			if(max<memo[i]) {
				max = memo[i];
			}
			if(max2<memo2[i]) {
				max2 = memo2[i];
			}
		}
		
		bw.write(Math.max(n-max, n-max2)+"");
		bw.close();
	}
}
class pair{
	int a;
	int b;
	public pair(int a, int b){
		this.a=a;
		this.b=b;
	}
	void print() {
		System.out.println(a + " " + b);
	}
}