[BOJ] 백준 2643 : 색종이 올려 놓기 (java)

🧪 2643 색종이 올려 놓기

---

난이도 : 🌟 골드 4
유형 : 동적 프로그래밍 (DP)

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. 회전이 가능하기 때문에 처음부터 큰 쪽을 가로에 넣어준다.

 

🧐 핵심 로직

---

1. 값을 입력받을 때 회전이 가능하기 때문에 더 큰쪽이 가로로 오도록 리스트에 값을 대입
2. 리스트를 오름차순으로 정렬
3. 최장 증가 부분 수열을 활용하여 dp의 최대값을 구한다

 

💻 최종 코드 (128 ms)

---

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

public class Main {

    static class Coordinate implements Comparable<Coordinate> {

        int x, y;

        Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Coordinate o) {

            if (this.x == o.x) {
                return o.y - this.y;
            }

            return o.x - this.x;
        }
    }

    static List<Coordinate> coordinates;

    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        int n = Integer.parseInt(br.readLine());
        int res = Integer.MIN_VALUE;
        int[] dp = new int[n + 1];
        coordinates = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            if (x > y) {
                coordinates.add(new Coordinate(x, y));
            } else {
                coordinates.add(new Coordinate(y, x)); // y가 더 큰 경우 90도 돌려서 가로로 취급한다.
            }
        }

        Collections.sort(coordinates);

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (coordinates.get(i).x <= coordinates.get(j).x && coordinates.get(i).y <= coordinates.get(j).y) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            res = Math.max(res, dp[i]);
        }

        System.out.println(res);

        br.close();
    }
}