[SWEA - 1812] D5 - 수정이의 타일 자르기

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

SW Expert Academy

1. 유형

우선순위큐, 구현

 

2. 풀이

• 크기가 가장 큰 타일부터 만들기
• 타일을 만들고 남은 짜투리들은 우선순위큐에 넣기
• 우선순위큐 때문에 크기가 가장 큰 타일이 먼저 나옴
• 위 과정을 반복

입력되는 값들을 내림차순을 만든다

문제를 풀때 자투리 타일을 우선순위큐에 저장해야 하는데 아래처럼 타일을 만들고 남은

파란색과 초록색을 저장해야 한다.

* 버리면 안되다고 한 부분은 

예를들어

2 0 0 0 이라는 입력값이 남았고, 높이1, 가로3인 타일이 pq에 들어있다고 치자

 

1*3타일로는 한변이 4인 타일을 만들 수 없다.

 

하지만 뒤에 한변이 1 짜리인 타일에서 쓰일 수 있다.

 

그래서 temp큐에 따로 모아놓고 반복이 끝난 후, 다시 pq에 집어 넣는것이다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int T, N, M;

	static class Pair implements Comparable<Pair> {
		int r, c;

		public Pair(int r, int c) {
			this.r = r;
			this.c = c;
			// TODO Auto-generated constructor stub
		}

		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			int tmp = this.r * this.c;
			int tmp2 = o.r * o.c;
			return tmp2 - tmp;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		T = Integer.valueOf(st.nextToken());
		for (int tc = 1; tc <= T; tc++) {
			PriorityQueue<Pair> pq = new PriorityQueue<>();
			st = new StringTokenizer(in.readLine(), " ");
			N = Integer.valueOf(st.nextToken());
			M = Integer.valueOf(st.nextToken());
			pq.add(new Pair(M, M));
			st = new StringTokenizer(in.readLine(), " ");
			Integer arr[] = new Integer[N];
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.valueOf(st.nextToken());
			}
			Arrays.sort(arr, new Comparator<Integer>() {
				@Override
				public int compare(Integer o1, Integer o2) {
					// TODO Auto-generated method stub
					return o2 - o1;
				}
			});
			int cnt = 1;
			for (int i = 0; i < N; i++) {
				int k = go(arr[i]);
				Queue<Pair> temp = new LinkedList<>();
				boolean flag=false;
				while (!pq.isEmpty()) {
					Pair cur = pq.peek();
					if (k <= cur.r && k <= cur.c) {
						flag=true;
						pq.poll();
						pq.add(new Pair(cur.r - k, cur.c));
						pq.add(new Pair(k, cur.c - k));	
						break;
					} else {
						temp.add(pq.poll());
					}
				}
				while(!temp.isEmpty()) {
					pq.add(temp.poll());
				}
				if(!flag) {
					cnt++;
					pq.add(new Pair(M - k, M));
					pq.add(new Pair(k, M - k));
				}
			}
			System.out.println("#" + tc + " " + cnt);
		}
	}

	static int go(int l) {
		int k = 1;
		if(l==0) return 1;
		for (int i = 0; i < l; i++) {
			k = k * 2;
		}
		return k;
	}
}

 

4. 풀이

조건을 잘 읽는 버릇을 들이자