[백준/1493] 박스 채우기 (Python)

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

1493번: 박스 채우기

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:27:39

 

---

 

문제 설명

 

 

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

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

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

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

 

출력

 

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

 

입력 예시

 

4 4 8
3
0 10
1 10
2 1

 

출력 예시

 

9

 

 

---

 

풀이

 

우선, 하위 큐브로 상위 큐브를 대체할 수 있다는 점에 주목하자(예를 들어 4x4x4 큐브 8개로 8x8x8 큐브를 대체 가능하다). 즉 크기가 큰 큐브를 가급적 사용하는 것이 유리하다는 사실을 알 수 있으므로 그리디하게 풀어 볼 수 있겠다. 

 

또한, 이 문제는 분할 정복을 통해 접근할 수있다. 임의의 (l, w, h)의 가로, 세로, 높이를 가진 빈 공간에, 블록 크기가 b인 블록으로 직사각형 형태로채웠다고 가정하자. 이 때, 가로 l'개, 세로 w'개를 사용하였다면 채운 블록의 부피는 (l'*b, w'*b, b)가 된다.

즉 남은 공간을 세 영역으로 나눠볼 수도 있겠다. 이를테면 (l - l'b, w, b), (l'b, w - w'b, b), (l, w, h - b) 세 영역으로 나눠볼 수 있다. (세 영역으로 나누는 법은 이외에도 꽤 있다) 즉 채운 블록을 제외한 나머지 블록으로 남은 위 세 공간을 채우는 작은 문제들로 분할할 수 있고, 나머지 블록으로 채울 수 있다면 사용한 블록의 값을, 그렇지 않다면 -1을 출력하면 된다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

L, W, H = map(int, input().split())
tot_volumn = L*W*H
N = int(input())
num_blocks = [0]*N
for _ in range(N) :
  i, a = map(int, input().split())
  num_blocks[i] = a

def div_and_con(l, w, h) :
  if l == 0 or w == 0 or h == 0 :
    return 0
  result = 0
  for i in range(N-1, -1, -1) :
    if not num_blocks[i] :
      continue
    boxlen = 2 ** i
    if not (l >= boxlen and w >= boxlen and h >= boxlen) :
      continue
    lnum, wnum = l // boxlen, w // boxlen
    if num_blocks[i] > lnum * wnum :
      base = lnum * wnum
    elif num_blocks[i] >= lnum :
      wnum = num_blocks[i] // lnum
      base = lnum * wnum
    else :
      wnum = 1
      lnum = num_blocks[i]
      base = num_blocks[i]

    num_blocks[i] -= base
    result += base
    left_l, left_w = l - lnum * boxlen, w - wnum * boxlen
    result += div_and_con(left_l, w, boxlen)
    result += div_and_con(l - left_l, left_w, boxlen)
    result += div_and_con(l, w, h - boxlen)
    return result
  return float('inf')

ans = div_and_con(L, W, H)
print(ans if ans < float('inf') else -1)

풀이 완료!