[백준 02643] 색종이 올려 놓기 [Java]

문제

http://boj.ma/2643

2643번: 색종이 올려 놓기

 

---

풀이

문제 요약

N개의 직사각형 종이를 자신보다 크거나 같은 종이 위에만 쌓아 가장 높게 쌓을 때의 높이를 구하자.

아이디어

종이는 서로의 변에 대해 평행하게만 놓을 수 있으므로 (작은 변의 길이, 큰 변의 길이)를 기준으로 입력받고, 오름차순으로 정렬하자.

public class Main {
	private static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = Math.min(x, y);
			this.y = Math.max(x, y);
		}
	}

		A.sort((a, b) -> {
			if (a.x == b.x) {
				return Integer.compare(a.y, b.y);
			}
			return Integer.compare(a.x, b.x);
		});

각 종이는 자기 자신에 대해 유효하며, 자신보다 큰 종이 위에 놓는 2차원 LIS로 볼 수 있다. 종이는 최대 100개로 이전 종이를 확인할 시간은 충분하다.

		int[] dp = new int[N];
		Arrays.fill(dp, 1);
		
		int res = 0;
		for (int i = 1; i < N; ++i) {
			for (int j = 0; j < i; ++j) {
				if (A.get(i).x >= A.get(j).x && A.get(i).y >= A.get(j).y) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			res = Math.max(res, dp[i]);
		}

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/02643.java

problem-solving/baekjoon-online-judge/normal/02643.java at main · rogi-rogi/problem-solving