[SWEA] D5 1812 수정이의 타일 자르기 (java)

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yGVsKC0YDFAUx&categoryId=AV4yGVsKC0YDFAUx&categoryType=CODE

SW Expert Academy

 

풀이

 

1) 필요한 정사각형을 배열에 담음

2) Tile클래스 생성. <- min값과 max값중 min값을 정렬기준으로함 (Comparable)

3) 우선순위큐<Tile> 에 M*M 타일을 넣음 (시작엔 무조건 하나 들어있어야 함)

4) 우선순위큐에서 poll()을 조지면 가장 큰 Tile이 나옴.(정확히는 min이 가장 큰.)

5) 정사각형 배열에서 크기가 큰 순서대로 4번의 min 값과 비교.

6) min 값보다 작으면 타일이 쪼개지고 2개추가

7) min 값보다 크면 뺐던거 도로 쑤셔넣고(offer) 새거 추가 (M*M)

8) 새거 추가할 때 마다 answer+1

 

주의사항

 

1) 정사각형 배열에 입력값을 넣는게 아니라 2^입력값 을 넣어야함

2) 배열을 정렬해야함

 

package com.SWEA;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
/**
 * @author yhs
 * @date 2020. 12. 3
 * @see
 * @mem
 * @time
 * @caution
 * [고려사항]
 * 먼저 입력받은 타일들을 크기순으로 정렬
 * 맨처음 M*M의 타일을 가져와서 위의 제일큰놈 크기로 자름
 * 그러면 M * (M-s)
 * [입력사항]
 * [출력사항]
 */
 
public class SWEA_D5_1812_수정이의타일자르기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int T,N,M;
	static PriorityQueue<Tile> pq;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(input.readLine());
		for(int t=1; t<=T; t++) {
			pq = new PriorityQueue<Tile>();
			int answer = 0;
			tokens = new StringTokenizer(input.readLine());
			N = Integer.parseInt(tokens.nextToken());
			M = Integer.parseInt(tokens.nextToken());
			int arr[] = new int[N];
			
			tokens = new StringTokenizer(input.readLine());
			for(int n=0; n<N; n++) {
				int side = Integer.parseInt(tokens.nextToken());
				arr[n] = (int) Math.pow(2, side);
			}
			
			Arrays.sort(arr);
			
			pq.offer(new Tile(M, M)); // 처음엔 무조건 타일 한장을 사야함
			answer++;
			
			for(int i=N-1; i>=0; i--) {
				Tile tile = pq.poll();
				if(tile.min >= arr[i] ) {
					pq.offer(new Tile(tile.min-arr[i], arr[i]));
					pq.offer(new Tile(tile.min, tile.max-arr[i]));
				}else {
					pq.offer(tile);
					pq.offer(new Tile(M-arr[i], arr[i]));
					pq.offer(new Tile(M, M-arr[i]));
					answer++;
				}
			}
			System.out.println("#"+t+" "+answer);
		}
	}
	
	static class Tile implements Comparable<Tile>{
		int min;
		int max;
		
		public Tile(int width, int height) {
			this.min = Math.min(width, height);
			this.max = Math.max(width, height);
		}
		@Override
		public int compareTo(Tile o) {
			return o.min - this.min;
		}
		
		@Override
		public String toString() {
			return "Tile [min=" + min + ", max=" + max + "]";
		}
		
 
	}
 
	static String src =
			""; 
			
}