백준 2643 색종이 올려놓기 java (dp)

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

2643번: 색종이 올려 놓기

 

1. 가장 기본 아이디어는 오름차순 정렬을 한 후, 가장 큰 종이가 있는 맨 뒤부터 접근을 한다.

 

2. 앞 종이가 뒷 종이의 범위를 벗어나더라도 90도 돌렸을 때는 만족하는 경우가 있는데 이것을 for문 내에서 잡아준다.

 

3. 아래 조건에서 paperSize[j][0] <= paperSize[j][0]은 왜 포함시켜주지 않는지 궁금할 수 있는데, 필요 없다.

이미 해당 변의 길이는 정렬을 했기 때문이다. 

if(paperSize[j][1] <= paperSize[i][1]
|| paperSize[j][1] <= paperSize[i][0] && paperSize[j][0] <= paperSize[i][1])

 

4. 일반적인 인덱스 정렬  뿐만 아니라, 아래처럼 가로 세로 정렬을 해주었는데, 이것은 꼭 필요하다.

위의 1~3번만 수행했을 때, 반례가 존재하기 때문이다.

// 가로 세로 정렬
for(int i=0; i<n; ++i){
    if(paperSize[i][0] < paperSize[i][1]){
        int temp = paperSize[i][0];
        paperSize[i][0] = paperSize[i][1];
        paperSize[i][1] = temp;
    }
}

 

반례)

2

13 14

14 12

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] paperSize = new int[n][2]; // 0: 가로, 1: 세로
        StringTokenizer st;
        for(int i=0; i<n; ++i){
            st = new StringTokenizer(br.readLine());
            paperSize[i][0] = Integer.parseInt(st.nextToken());
            paperSize[i][1] = Integer.parseInt(st.nextToken());
        }

        // 가로 세로 정렬
        for(int i=0; i<n; ++i){
            if(paperSize[i][0] < paperSize[i][1]){
                int temp = paperSize[i][0];
                paperSize[i][0] = paperSize[i][1];
                paperSize[i][1] = temp;
            }
        }

        // 인덱스 정렬
        Arrays.sort(paperSize, (e1, e2) -> {
            if(e1[0] == e2[0]) return e1[1] - e2[1];
            else return e1[0] - e2[0];
        });

        int ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 해당 i번째 종이는 무조건 포함된다.

        for(int i=n-1; 0<i; --i){
            for(int k=1; k<=i; ++k){
                int j = i - k;
                if(paperSize[j][1] <= paperSize[i][1]
                || paperSize[j][1] <= paperSize[i][0] && paperSize[j][0] <= paperSize[i][1]){
                    dp[j] = Math.max(dp[j], dp[i]+1);
                    ans = Math.max(dp[j], ans);
                }
            }
        }

        System.out.print(ans);
    }
}