BAEK_2643_색종이 올려놓기

17 Sep 2019 in Sidemenu / BaekJoon

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

2643. 색종이 올려놓기

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main{
	static int N, x, y, max=Integer.MIN_VALUE;
	static int[] dp;
	public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		dp = new int[N];
		ArrayList<int[]> list = new ArrayList<int[]>();
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			if(x>=y) {
				list.add(new int[] {x,y});
			}else {
				list.add(new int[] {y,x});
			}
		}	
		Collections.sort(list, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]<o2[0]) return 1;
				else if(o1[0]>o2[0]) return -1;
				else if(o1[1]<o2[1]) return 1;
				else if(o1[1]>o2[1]) return -1;
				return 0;
			}
		});
		for(int i=0; i<N; i++) {
			int[] p1 = list.get(i);
			for(int j=0; j<i; j++) {
				int[] p2 = list.get(j);
				if((p1[0]<=p2[0]&&p1[1]<=p2[1])) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
			if(max<dp[i]) max=dp[i];
		}
		System.out.println(max+1);
	}
}