1493. 박스 채우기

INFO

링크: 문제 보러가기

언어: Java

난이도: 2

알고리즘: 그리디 분할정복

소요 시간: ❌

1. 문제 이해

핵심 요구사항

length × width × height 크기의 박스가 주어짐
해당 박스를 정육면체 큐브(2의 제곱꼴)로 재워야함

출력: 큐브의 최소 개수 || -1

제한 조건

변수 범위 → 특정 경우에 Long 타입을 써야할
- $1 \leq l e n g t h, w i d t h, h e i g h t \leq 1 0^{6}$
- $1 \leq n \leq 20$
- $0 \leq A i < 20$
- $0 \leq B i \leq 1 0^{6}$
시간: 2초
메모리: 128MB

2. 사고의 흐름 (Thinking)

❌ 1차 시도: 분할정복(기하학적) + 7개로 분할
- 주어진 박스 공간 (L, W, H) 에서 가장 큰 가능한 큐브를 (0, 0, 0) 좌표에 배치.
- 남는 공간은 7개의 정육면체로 분할히여 재귀적으로 해결.
- 분할 영역:
  - 배치한 큐브의 오른쪽
  - 배치한 큐브의 뒤쪽
  - 배치한 큐브의 오른쪽, 뒤쪽
  - 배치한 큐브의 위쪽
  - 배치한 큐브의 위쪽, 오른쪽
  - 배치한 큐브의 위쪽, 뒤쪽
  - 배치한 큐브의 위쪽, 오른쪽, 뒤쪽
- ⇒ 분할 영역오류:
  1. 겹치는 부분을 제대로 체크 안함
```
fillCube(x+c, y, z, l-c, w, h); // x
fillCube(x, y+c, z, l, w-c, h); // y
fillCube(x, y, z+c, l, w, h-c); // z
// 생략
```
    - 재귀 호출 시 인자로 넘기는 l, w, h에 대해 위에서 이미 체크한 공간을 신경 쓰지 않고 넘겨서 공간이 중복 계산됨.
  2. 불필요하게 많은 조각으로 나눔.
❌ 2차 시도: 분할정복(기하학적) + 3개로 분할
- 1차 시도와 동일하나, 남는 공간은 겹치지 않는 3개의 정육면체로 분할히여 재귀적으로 해결.
- 분할 영역
  - 배치한 큐브의 오른쪽 전체
  - 배치한 큐브의 뒤쪽 (오른쪽 제외)
  - 배치한 큐브의 위쪽(오른쪽, 뒤쪽 영역 제외)
- ⇒ 시간 초과
  - 주어진 박스 공간이 최대 $(1 0^{6})^{3}$ 의 크기를 가짐.
  - 만일 큐브 종류가 1x1x1밖에 없다면, 모든 공간을 해당 크기로 분할해 채워야함
  - 즉, $(1 0^{6})^{3}$ 칸을 전부 한번씩 처리해야한다는 문제가 발생 → 시간 초과
✅ 3차 시도: 분할정복(기하학적) + 3개로 분할 + 1x1x1 예외처리
- 1x1x1인 큐브는 따로 관리
- 1x1x1보다 더 큰 큐브들을 사용할 수 없을 때, 더이상 박스공간을 분할하지 않고
- 현재 탐색 중인 공간 부피(l*w*h)를 계산해서 한번에 처리
  - 이때, l*w*h는 최악의 경우 $(1 0^{6})^{3}$ 이므로, int 범위 내에서 감당 불가 → long으로 계산
✏️ (예정) 4차 시도: 수학적 분할정복
- 공간을 썰지 않고, 부피와 개수만 계산하는 경우도 가능하다함.

3. 풀이 및 코드 (Solution)

방법 1: 분할정복(기하학적)

탐욕적 기법(Greedy)을 사용하여 현재 공간에 들어갈 수 있는 가장 큰 큐브를 우선 배치하고, 남은 공간을 겹치지 않는 3개의 직육면체로 분할하여 재귀 호출(분할 정복) 수행

import java.io.*;
import java.util.*;
public class Main {
    static int length, width, height, N;
    static long oneCube = 0;
    static Map<Integer, Integer> cubes = new TreeMap<>(Collections.reverseOrder());   // key 기준 정렬
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        length = Integer.parseInt(temp[0]);
        width = Integer.parseInt(temp[1]);
        height = Integer.parseInt(temp[2]);
 
        N = Integer.parseInt(br.readLine());
        int cube, cnt;
        for (int n=0; n<N; n++) {
            temp = br.readLine().split(" ");
            cube = Integer.parseInt(temp[0]);
            cnt = Integer.parseInt(temp[1]);
            if (cube == 0) oneCube = cnt;
            else cubes.put(cube, cnt);
 
        }
 
        System.out.println(fillCube(0,0,0,length,width,height));
    }
 
    static int fillCube(int x, int y, int z, int l, int w, int h) {
        if (l <= 0 || w <= 0 || h <= 0) return 0;
 
        // 남아있는 가장 큰 큐브로 채우기
        int result = 0;
        int min = l > w ? (w > h ? h : w) : (l > h ? h : l);
        int c = 0;
 
        for (int cube : cubes.keySet()) {
            c = (int) Math.pow(2,cube);
            if (c <= min && cubes.get(cube) != 0) {
                result ++;
                int cubeCnt = cubes.get(cube) - 1;
                if (cubeCnt == 0) {
                    cubes.remove(cube);
                } else {
                    cubes.put(cube, cubeCnt);
                }
                break;
            }
        }
        
        if (result == 0) {
            oneCube -= (long) l*w*h;
            result += (long) l*w*h;
            if (oneCube < 0) return -1;
            else return result;
        }
 
        // 나머지 부분 정육면체 형태로 분할해서 fillCube 호출
        // 만일 중간에 호출한 결과가 -1이면 -1 return
        // 오른쪽
        int cnt;
        cnt = fillCube(x+c, y, z, l-c, w, h); // x
        if (cnt == -1) return -1;
        else result += cnt;
 
        // 오른쪽 제외 뒤쪽
        cnt = fillCube(x, y+c, z, c, w-c, h); // x
        if (cnt == -1) return -1;
        else result += cnt;
 
        // 똑같은 xy의 위쪽
        cnt = fillCube(x, y, z+c, c, c, h-c); // x
        if (cnt == -1) return -1;
        else result += cnt;
 
        // 아니면 호출한 결과끼리 더하고 + 1해서 return
        return result;
    }
}

시간 복잡도: $O (u se d C u b e * N)$
- 박스에 채워넣는 큐브의 개수만큼 재귀가 발생.
- 큐브를 채워넣을 때, 큐브(N)의 종류를 탐색하므로 시간복잡도는 $O (u se d C u b e * N)$ 이다.

자료형

oneCube -= (long) l*w*h;
result += (long) l*w*h;
  ```
- `l*w*h`가 최대 $10^{18}$ 로 int 범위를 넘어갈 수 있기때문에 long 사용

4. 회고 (Retrospective)

Computer PS

☀️ Log

1. 문제 이해

핵심 요구사항

제한 조건

2. 사고의 흐름 (Thinking)

3. 풀이 및 코드 (Solution)

방법 1: 분할정복(기하학적)

4. 회고 (Retrospective)

탐색기

목차