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

www.acmicpc.net/problem/2643

2643번: 색종이 올려 놓기

 

1. 문제 설명

 

색종이들의 가로, 세로 길이가 주어질 때 조건을 만족하면서 쌓을 수 있는 최대 색종이 장수를 구하는 문제이다.

 

조건 1. 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다.

조건 2. 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다.

 

2. 풀이

 

DP를 이용해서 풀 수 있는 문제이다.

 

색종이들의 길이들을 저장하고 그 길이들을 오름차순 정렬한다. 

 

그 후 LIS 알고리즘으로 최대 색종이 장수를 구하면 된다.

 

시간 복잡도  : O(n^2)

 

 

 

3. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {



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

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int paper_num = Integer.parseInt(br.readLine());

        int[][] paper=new int[paper_num][2];
        int[] cache=new int[paper_num];
        int max=0;

        for(int x=0;x<paper_num;x++){
            StringTokenizer st=new StringTokenizer(br.readLine()," ");

            int temp=Integer.parseInt(st.nextToken());
            int temp2=Integer.parseInt(st.nextToken());

            if(temp<temp2){
                int temp3=temp;
                temp=temp2;
                temp2=temp3;
            }

            paper[x][0] = temp;
            paper[x][1] = temp2;

        }

        Arrays.sort(paper, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0])
                    return o1[1]-o2[1];
                else
                    return o1[0]-o2[0];
            }
        });



        for(int x=0;x<paper_num;x++){
            cache[x] = 1;

            for(int y=0;y<x;y++){
                if(paper[y][0]<=paper[x][0] && paper[y][1]<=paper[x][1] && cache[x]<cache[y]+1)
                    cache[x]=cache[y]+1;
            }

            if(max<cache[x])
                max=cache[x];
        }

        bw.write(String.valueOf(max));

        bw.flush();
        br.close();
        bw.close();

    }

}