[Python/파이썬] 백준 1493번 박스 채우기

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

 

코드

import sys
input = sys.stdin.readline

l, w, h = map(int, input().split())
n = int(input())
cubes = []
for _ in range(n):
    a, b = map(int, input().split())
    cubes.append([2**a, b])


def dc(l, w, h, idx):   # 분할정복
    if idx == -1:   # 큐브 부족
        print(-1)
        exit()
    res = 0
    # idx번째 큐브의 필요 개수
    need = (l//cubes[idx][0])*(w//cubes[idx][0]) * (h//cubes[idx][0])
    if need <= cubes[idx][1]:   # 남은 큐브로 처리 가능
        res += need
        cubes[idx][1] -= need
    else:   # 남은 큐브 개수로는 부족 => 더 작은 큐브들로 채우기
        lack = need-cubes[idx][1]
        res += cubes[idx][1]
        cubes[idx][1] = 0
        res += dc(cubes[idx][0]*lack, cubes[idx][0], cubes[idx][0], idx-1)

    if h % cubes[idx][0] > 0:   # 위
        res += dc(l, w, h % cubes[idx][0], idx-1)
    if w % cubes[idx][0] > 0:   # 옆
        res += dc(l, w % cubes[idx][0], h-h % cubes[idx][0], idx-1)
    if l % cubes[idx][0] > 0:   # 뒤
        res += dc(l % cubes[idx][0], w-w %
                  cubes[idx][0], h-h % cubes[idx][0], idx-1)
    return res


print(dc(l, w, h, n-1))

 

큰 박스로 최대한 채우고, 남은 부분은 그 다음으로 큰 박스로 최대한 채우고, 또 남은 부분은 그 다음으로 큰 박스로 채우고...하는 과정을 반복하는 것이다.

 

단계별로 설명하자면

1. l × w × h 크기의 박스에 idx번째 큐브(한 변 길이: 2^idx)를 몇 개 넣을 수 있는지 확인한다. 이 수(need)보다 갖고 있는 큐브의 수(cubes[idx][1])가 많다면 필요한만큼 사용하면 되지만, 필요한 개수만큼 없다면 부족한 개수(lack)는 더 작은 큐브들로 채워야 한다. (현재 큐브의 크기)×(부족한 개수)는 더 작은 큐브로 채워주기 위해 dc(cubes[idx][0]*lack, cubes[idx][0], cubes[idx][0], idx-1)를 재귀호출한다.

 

2. 그리고 남은 부분들을 위, 옆, 뒤 3부분으로 나누어서  더 작은 큐브들로 채워줄 것이다. 

 

그림과 같이 ①위, ②옆, ③뒤로 나누어서 다시 idx-1만한 큐브들로 채워준다. (편의상 남는 부분들이 idx번째 큐브의 한 변보다 크게 그렸지만, 1번 과정에서 idx번째 크기 큐브들로 최대한 채운다고 가정했으므로 실제로는 이렇지 않고, 가로, 세로, 높이 모두 idx번째 큐브의 한 변인 cubes[idx][0]으로 나눈 나머지 정도만 남는다.)

 

이 과정을 반복하다가 idx가 -1이 나올 때까지 가면 cube의 개수가 부족하여 처음에 주어진 박스를 다 채울 수 없다는 말이므로 -1을 출력하고 프로그램을 종료한다. 그렇지 않다면 각 단계에서 나오는 큐브들의 개수를 모두 더하여 출력하면 된다.