셋째 줄부터 총 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)