색종이 올려놓기 [백준 2643][골드4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

2643번: 색종이 올려 놓기

DP 문제다.

색종이를 정렬하고

각 색종이 마다 자신한테 올려 놓을 수 있는 최대의 색종이 수를 구해서 활용하였다.

DP는 어렵다.

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

class Paper implements Comparable<Paper>{
	int width , height;
	
	public Paper(int width, int height) {
		this.width = width;
		this.height = height;
	}

	@Override
	public int compareTo(Paper o) {
		if(this.width == o.width) {
			return Integer.compare(this.height, o.height);
		}
		return Integer.compare(this.width, o.width);
	}
}
public class Main {
	public static int cnt=0;
	public static int[] DP = new int[1000];
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		Paper[] p = new Paper[N];
		
		for (int i = 0; i < N; i++) {
			
			int w= sc.nextInt();
			int h= sc.nextInt();
			if(w < h) {
				int temp = w;
				w = h;
				h = temp;
			}
			p[i] = new Paper(w, h);
		}
		Arrays.sort(p);
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < p.length; i++) {
			if(p[i].width <=0 || p[i].height<=0) continue;
			for (int j = 0; j < i; j++) {
				if(p[i].width >= p[j].width && p[i].height >= p[j].height) {
					DP[i] = Math.max(DP[i], DP[j]);
				}
			}
			DP[i]++;
			max = Math.max(DP[i], max);
			
		}
		System.out.println(max);
	}

}