[백준]#2643 색종이 올려 놓기

문제

크기가 모두 다른 직사각형 모양의 색종이가 여러 장 있다. 색종이를 하나씩 올려 놓아, 되도록 많은 장수의 색종이들을 쌓으려고 한다.

새로 한 장의 색종이를 올려 놓을 때는 지금까지 쌓아 놓은 색종이들 중 맨 위의 색종이 위에 올려놓아야 하며 아래의 두 조건을 모두 만족해야 한다.

• 조건 1 : 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다. 즉, 맨 위의 색종이 밖으로 나가지 않아야 한다.
• 조건 2 : 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다.(색종이를 90˚돌려 놓을 수 있다.)
• 예를 들어, 아래의 그림 중에서 위의 두 조건을 모두 만족하는 경우는 (나)뿐이다.

색종이는 두 변의 길이로 표현된다. (3, 5)는 두 변의 길이가 각각 3과 5인 색종이를 나타낸다. 예를 들어, 다음과 같이 7장의 색종이가 주어졌다고 하자 : (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12) 위의 조건을 만족하면서 가장 많이 쌓을 수 있는 색종이들의 순서는 (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2)이다.

입력으로 색종이들이 주어졌을 때, 위의 조건 1과 조건 2를 만족하면서 쌓을 수 있는 최대 색종이 장수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 작은 자연수이다.

출력

쌓을 수 있는 최대 색종이 장수를 출력한다.

예제 입력 1

7
1 2
8 7
20 10
20 20
15 12
12 14
11 12

예제 출력 1

6

풀이

이 문제는 다이나믹 프로그래밍 알고리즘을 이용해서 풀 수 있었다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.PriorityQueue;

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());
        PriorityQueue<Rect> queue = new PriorityQueue<>();
        Rect[] arr = new Rect[N];
        int[] dp = new int[N];

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            int r = Integer.parseInt(input[0]);
            int c = Integer.parseInt(input[1]);

            if(r<c)
                queue.add(new Rect(c, r));
            else
                queue.add(new Rect(r, c));
        }

        int idx = 0;
        while(!queue.isEmpty()) {
            Rect attach = queue.poll();

            arr[idx] = new Rect(attach.r, attach.c);
            idx++;
        }


        for(int i=0; i<N; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[i].r<=arr[j].r && arr[i].c<=arr[j].c)
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i=0; i<N; i++)
            max = Math.max(max, dp[i]);
        System.out.println(max);
    }

    public static class Rect implements Comparable<Rect>{
        int r;
        int c;

        public Rect(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public int compareTo(Rect r) {
            if(this.r==r.r)
                return this.c < r.c ? 1 : -1;

            return this.r <  r.r ? 1 : -1;
        }
    }
}