정올_1510 색종이 올려 놓기(자바) / 동적 계획법

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.jungol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class jungol_1510 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		ArrayList<Paper> pa = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int tmp1 = Integer.parseInt(st.nextToken());
			int tmp2 = Integer.parseInt(st.nextToken());
			if(tmp1>tmp2) {				
				pa.add(new Paper(tmp1, tmp2));
			}else{
				pa.add(new Paper(tmp2, tmp1));
			}
		}
		Collections.sort(pa);
		int ans=0;
		int[] dp = new int [N];
		for (int i = 0; i < N; i++) {
			Paper now = pa.get(i);
			for (int j = 0; j < i; j++) {
				Paper next = pa.get(j);
				if(now.lar>=next.lar && now.sma>=next.sma) {
					dp[i]=Math.max(dp[i],dp[j]);
				}
			}
			dp[i]++;
			ans=Math.max(ans, dp[i]);
		}
		
		System.out.println(ans);
		
	}
	
	static class Paper implements Comparable<Paper>{
		int lar;
		int sma;
		public Paper(int lar, int sma) {
			super();
			this.lar = lar;
			this.sma = sma;
		}
		@Override
		public int compareTo(Paper o) {
			if(this.lar==o.lar) {
				return this.sma-o.sma;
			}
			return this.lar-o.lar;
		}
	}
}

 

- 색종이 올려 놓기 문제는 겹치지 않게 최대한 많은 색종이를 세는 문제입니다.

 

- 색종이의 길이를 긴 크기, 작은 크기로 분리하여 클래스에 담아줍니다.

 

- 색종이를 Comparable를 통해서 큰 길이를 먼저 비교 해서 정렬을 하고, 큰 길이가 같으면 작은 길이를 비교해서 정렬합니다.

 

- for문을 통해서 dp를 이용해서 최적의 갯수를 구하는 로직을 작성해주면 됩니다.