백준 2643번: 색종이 올려 놓기

문제 설명

• https://www.acmicpc.net/problem/2643
• N개의 색종이를 최대한 많이 쌓아야 합니다.
  아래 색종이보다 두 변의 길이가 모두 작아야 쌓을 수 있습니다.
  색종이는 90도 회전만 가능하며 비스듬히 놓을 수 없습니다.

접근법

• 크기가 큰 색종이부터 아래에 쌓는게 유리합니다. 크기의 기준이 가로인지 세로인지 가로x세로인지 모호합니다. 그래서 이를 다른 색종이 위에 쌓을 수 없는(쌓는 게 불리한) 색종이를 먼저 확인하는 게 유리하다라고 생각했습니다.
  가로 또는 세로의 최댓값이 클수록 다른 색종이 위에 쌓을 때 불리합니다. 여기서 가로 또는 세로가 가능한 이유는 문제에서 색종이를 90도 회전하는 게 가능하다고 했기 때문입니다.

• 정답을 구하기 위해 dp배열을 활용했습니다. dp[i] = 0~i까지의 색종이를 이용해 i번째 색종이를 가장 높게 쌓았을 때의 높이라고 정의했습니다. 이는 LIS를 구할 때와 동일한 방식으로 i보다 작은 j를 모두 순회하면서 j번째 높이 + 1이 가장 큰 값이 dp[i]의 값이 됩니다.
  또한 max(j번째 높이 + 1)인 j가 여러개 있다면 다음에 쌓기에 유리한(조금이라도 크기가 큰) 색종이를 선택합니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int N = Integer.parseInt(br.readLine());
		List<int[]> board = new ArrayList<int[]>();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			board.add(new int[] {a,b});
		}
		Collections.sort(board, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// 90도 회전이 가능하기 때문에 가로 또는 세로 중 더 긴 값의 길이가 긴 순서로 정렬해야 됨
				return (Math.max(o2[0], o2[1])  ==  Math.max(o1[0], o1[1]))? (Math.min(o2[0], o2[1]) - Math.min(o1[0], o1[1])) : (Math.max(o2[0], o2[1]) - Math.max(o1[0], o1[1]));
			}
		});
		
		int[][] dp = new int[N][3];
		dp[0] = new int[] {board.get(0)[0],board.get(0)[1],1};
		int answer = 1;
		for (int i = 1; i < N; i++) {
			int[] nowPaper = board.get(i);
			int[] turnedPaper = new int[] {board.get(i)[1],board.get(i)[0]};
			dp[i] = new int[] {nowPaper[0],nowPaper[1],1}; // i번째의 초기값
			for (int j = 0; j < i; j++) {
				int[] beforePaper = dp[j];
				//nowPaper
				if(canOverlap(nowPaper,beforePaper)) {
					if(cumCntIsSameButPaperIsLargerThanBefore(dp[i],nowPaper,beforePaper[2]) || dp[i][2] < beforePaper[2]+1) {						
						dp[i] = new int[] {nowPaper[0],nowPaper[1],beforePaper[2]+1};
					}					
					answer = Math.max(answer, dp[i][2]);
				}
				//turnedPaper
				if(canOverlap(turnedPaper,beforePaper)) {
					if(cumCntIsSameButPaperIsLargerThanBefore(dp[i],turnedPaper,beforePaper[2]) || dp[i][2] < beforePaper[2]+1) {						
						dp[i] = new int[] {turnedPaper[0],turnedPaper[1],beforePaper[2]+1};
					}
					answer = Math.max(answer, dp[i][2]);
				}
			}
		}
		System.out.println(answer);

	}
	
	public static boolean cumCntIsSameButPaperIsLargerThanBefore(int[] candi, int[] nowPaper, int beforeCumCnt) {
		if(candi[2] == beforeCumCnt+1 && nowPaper[0] >= candi[0] && nowPaper[1] >= candi[1]) return true;
		return false;
	}
	
	public static boolean canOverlap(int[] nowPaper, int[] beforePaper) {
		if(nowPaper[0] <= beforePaper[0] && nowPaper[1] <= beforePaper[1]) return true;
		return false;
	}
	
}