[백준 - 1493번] 박스 채우기 - Java

문제 링크

https://www.acmicpc.net/problem/1493

문제

티어: 골드 2
알고리즘: 그리디, 수학, 분할 정복

입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력

첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

제한

• 1 ≤ length, width, height ≤ 106
• 1 ≤ n ≤ 20
• 0 ≤ Ai < 20
• 0 ≤ Bi ≤ 106
• Ai ≠ Aj (i ≠ j)

풀이

박스를 채우는 데 큐브의 개수를 최소로 해야 한다.

최소로 하기 위해서는 가장 큰 큐브부터 차례대로 채워야 한다.

왜냐하면 큰 큐브로 채울 수 있다면 그보다 작은 큐브로 채울 수 있는 공간을 최소 개수로 채울 수 있기 때문이다.

그 대신 차곡 차곡 채우는게 중요하다. (한쪽 공간이 남지 않게끔 그려보면 쉽게 이해됨)

그래서 l, w, h 박스의 들어갈 수 있는 가장 큰 큐브를 하나 찾는다.

이 큐브는 박스에 왼쪽 아래 모서리에 채워진다고 가정한다. (차곡 차곡 쌓기 위함)

그리고 해당 큐브로 높이를 최대한 채워준다. h / cubeLen 만큼 채워진다.

그러면 다시 채워야될 공간을 3개의 육면체 공간으로 나눌 수 있다.

첫 번째는 (l => cubeLen, w => cubeLen, h => h - h/cubeLen)

두 번째는 (l => l - cubeLen, w => cubeLen, h => h)

세 번째는 (l => l, w => w - cubeLen, h => h)

(직접 그려보면 이해가 쉽다.)

세 육면체 공간으로 나눠지는 이유는 나누기 전 원래 박스에서 사용된 가장 큰 큐브를 기준으로 나눠야 매번 최선의 선택을 할 수 있기 때문이다.(가장 큰 큐브를 선택하는 것)

각 육면체 공간은 새로운 박스로 정의될 수 있고, 이는 분할 정복 풀이가 된다.

만약 나눠진 어떠한 육면체 공간을 채울 수 없다면, 이 경우는 큐브로 박스를 채울 수 없는 경우이기 때문에 -1를 출력해 준다.

이 풀이는 최대 2천만 횟수(러프하게 잡아서)를 넘지 않기 때문에 시간 제한에 걸리지 않는다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] cube;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int l = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());
      int h = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(br.readLine());
      cube = new int[n];
      
      for(int i=0; i<n; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          st2.nextToken();
          cube[i] = Integer.parseInt(st2.nextToken()); 
      }
      System.out.println(answer(l, w, h));
  }
  
  static int answer(int l, int w, int h) {
      int i = maxCube(l, w, h);
      if(i == -1) {
          return -1;
      }
      int cl = (int) Math.pow(2, i);
      int cnt = h / cl;
      cnt = cnt <= cube[i] ? cnt : cube[i];
      cube[i] -= cnt;
      
      if(h - (cl * cnt) > 0) {
          int r = answer(cl, cl, h - (cl * cnt));
          if(r == -1) {
              return -1;
          }
          cnt += r;
      }
      
      if(l - cl > 0) {
          int r = answer(l - cl, cl, h);
          if(r == -1) {
              return -1;
          }
          cnt += r;
      }
      
      if(w - cl > 0) {
          int r = answer(l, w - cl, h);
          if(r == -1){
              return -1;
          }
          cnt += r;
      }
      
      return cnt;
  }
  
  static int maxCube(int l, int w, int h) {
      for(int i = cube.length - 1; i>=0; i--) {
          int cl = (int) Math.pow(2, i);
          if(0 < cube[i] && l >= cl && w >= cl && h >= cl ) {
              return i;
          }
      }
      //-1이면 불가능한 경우가 됨.
      return -1;
  }
}