제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1812 수정이의 타일자르기입니다.
포인트
개인적으로 해당 문제가 조금 어려웠습니다.
타일을 자를때 하나의 타일에서 여러 타일을 만들 수도 있고, 못만드는 경우를 고려해야합니다.
그래서 저는 잘랐을 때의 타일을 저장하기로 하였습니다.
PriorityQueue를 활용하여 가장 큰 길이를 가진 타일을 나오도록 만들었습니다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Q1812 {
static class Tile implements Comparable<Tile> {
int min, max;
public Tile(int a, int b) {
this.min = Math.min(a, b);
this.max = Math.max(a, b);
}
@Override
public int compareTo(Tile o) {
return Integer.compare(o.min, this.min);
}
}
private static int tc, N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
tc = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
for (int t = 1; t <= tc; t++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
Integer[] length = new Integer[N];
for (int i = 0; i < N; i++) {
int b = Integer.parseInt(st.nextToken());
length[i] = b;
}
Arrays.sort(length, Collections.reverseOrder());
PriorityQueue<Tile> pq = new PriorityQueue<>();
int ans = 1;
pq.add(new Tile(M, M));
for (int i = 0; i < N; i++) {
Tile tile = pq.poll();
int len = (1 << length[i]);
if (tile.min >= len) {
pq.add(new Tile(tile.max - len, tile.min));
pq.add(new Tile(tile.min - len, len));
} else {
pq.add(tile);
pq.add(new Tile(M - len, len));
pq.add(new Tile(M, M - len));
ans++;
}
}
sb.append("#").append(t).append(" ").append(ans).append("\n");
}
System.out.println(sb);
}
}코드 설명
static class Tile implements Comparable<Tile> {
int min, max;
public Tile(int a, int b) {
this.min = Math.min(a, b);
this.max = Math.max(a, b);
}
@Override
public int compareTo(Tile o) {
return Integer.compare(o.min, this.min); // 큰 min부터 우선
}
}- Tile 클래스 정의
- 분할된 타일의 가로 세로를 담고, min 기준으로 내림차순 정렬되게 Comparable을 구성받아 구현하였습니다.
- PriorityQueue에서 가장 적절한 위치에 타일을 배치하기 위한 기준입니다.
Arrays.sort(length, Collections.reverseOrder()); // 큰 타일부터 먼저 배치
PriorityQueue<Tile> pq = new PriorityQueue<>();
int ans = 1;
pq.add(new Tile(M, M));- 입력받은 length[i]는 타일의 크기를 2^k으로 표현합니다
- 큰 타일부터 배치하기 위해 내림차순 정렬합니다.
- 하나의 큰 정사각형(M×M)을 처음으로 넣어줍니다.
for (int i = 0; i < N; i++) {
Tile tile = pq.poll(); // 현재 가장 적절한 빈 공간
int len = (1 << length[i]); // 실제 타일 길이 (2^k)
if (tile.min >= len) {
// 현재 타일이 현재 빈 공간에 들어갈 수 있으면
pq.add(new Tile(tile.max - len, tile.min)); // 오른쪽 빈 공간
pq.add(new Tile(tile.min - len, len)); // 아래쪽 빈 공간
} else {
// 현재 타일이 안 들어가면 새 정사각형 추가
pq.add(tile); // 원래 꺼낸 공간 다시 넣기
pq.add(new Tile(M - len, len)); // 새 공간에서 남은 오른쪽
pq.add(new Tile(M, M - len)); // 새 공간에서 남은 아래쪽
ans++;
}
}- 타일을 배치하고 남은 공간을 다시 Tile 객체로 분할하여 pq에 저장
- 만약 현재 가장 큰 빈 공간에도 타일이 안 들어가면, 새로운 정사각형이 필요하다는 것으로
- 이 때 ans++ 해서 필요한 정사각형 개수를 증가합니다.
'코딩테스트 > SWExpert' 카테고리의 다른 글
| [코딩테스트] SWEA 5521 상원이의 생일파티(Java) (2) | 2025.07.03 |
|---|---|
| [코딩테스트] SWEA 3421 수제 버거 장인(Java) (0) | 2025.07.02 |
| [코딩테스트] SWEA 6782 현주가 좋아하는 제곱근 놀이(Java) (0) | 2025.07.02 |
| [코딩테스트] SWEA 7793 오! 나의 여신님(Java) (2) | 2025.07.02 |
| [코딩테스트] SWEA 1256 K번째 접미어(Java) (0) | 2025.07.01 |