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

1. 문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yGVsKC0YDFAUx

SW Expert Academy

2. 접근방법

타일을 큰거부터 꺼내서 만들어야 하고

남은 자투리 부분을 다시 잘 잘라서 다음에 쓸 수 있게 잘 넣어 둬야 하는 구현 문제

 

우선 큰거부터 꺼내 써야 하는 이유는

 

작은게 먼저 나오면 자투리 부분에서 쓸 수 있는게 있는지 전부 검사를 해야만 하지만

 

큰거 부터 꺼내면 지금 가진 것 중에 가장 큰 것과 비교해서

가능하면 그걸 쓰고 불가능하면 새거를 만드는 동작만 하면 되기 때문이다.

 

자투리를 어떻게 나누느냐는

 

정사각형에서 자르든 직사각형에서 자르든 똑같은 동작을 하면된다.

 

요렇게 잘랐을 때가 가장 효율적으로 타일을 자른 경우이다.

 

여기서 가로 세로 길이가 다르다면 항상 짧은 걸 기준으로 정렬이 되도록 해야한다.

 

한쪽 길이가 아무리 길어봐야 정사각형을 만드려면 짧은 쪽 길이가 기준이 되어야 하니

짧은 쪽 길이를 기준으로 잡히게 구현하자.

 

나는 자투리와 만들어야 하는 타일 모두 큰 수부터 나와야하므로

우선순위큐 2개를 이용하여 구현하였다.

 

타일을 만들 때 자투리 중 가장 큰 것으로 만들 수 없으면 새 것을 하나 추가하고

가장 큰 것으로 만들 수 있다면 그 것을 이용한 뒤

남은 자투리를 위와 같이 쪼개서 다시 우선순위 큐에 넣는 식으로 구현 하였다.

 

3. 자바 코드

package D5;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P1812수정이의타일자르기 {
	static PriorityQueue<Integer> tiles;
	static PriorityQueue<shape> newtiles;
	static int cnt, N, M;

	static class shape implements Comparable<shape> {
		int x;
		int y;

		public shape(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(shape o) {
			return o.x - this.x;
		}

	}

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int T;
		T = Integer.parseInt(st.nextToken());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			tiles = new PriorityQueue<Integer>(Collections.reverseOrder());
			newtiles = new PriorityQueue<shape>();
			cnt = 0;
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++)
				tiles.add(Integer.parseInt(st.nextToken()));
			make_tile();
			System.out.printf("#%d %d\n", tc, cnt);
		}
	}

	static void make_tile() {
		if (tiles.isEmpty()) {
			return;
		}
		if (newtiles.isEmpty()) {
			newtiles.offer(new shape(M, M));
			cnt++;
		}
		int tile = (int) Math.pow(2, tiles.poll()); // 지금 만들 타일
		if (newtiles.peek().x < tile) {
			cnt++;
			newtiles.offer(new shape(M, M));
		}
		shape newtile = newtiles.poll();

		if (newtile.x < newtile.y - tile)
			newtiles.offer(new shape(newtile.x, newtile.y - tile));
		else
			newtiles.offer(new shape(newtile.y - tile, newtile.x));

		if (newtile.x - tile < tile)
			newtiles.offer(new shape(newtile.x - tile, tile));
		else
			newtiles.offer(new shape(tile, newtile.x - tile));
		make_tile();
	}
}

4. 마치며

처음 생각해내는데 시간이 오래 걸렸는데

그림으로 그려가면서 확인하니 풀 수 있었다.

 

꽤나 재밌는 문제였다.