[백준] 박스 채우기

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

1493번: 박스 채우기

1. 문제 이해

length * width * height 크기를 가진 박스가 주어지고 이 박스를 채우기 위해 2의 지수승을 한변으로 가지는 정육면체로 채우려고 할 때 필요한 큐브의 최소 개수를 구하는 문제입니다.

2. 문제 접근

첫번째 접근: 냅색

효율적인 냅색으로 박스를 채울 수 있는 방법에 대해 고민해보았지만 박스의 크기가 10 ^ 6 * 10 ^ 6 * 10 ^ 6이기 때문에 불가능했습니다.

 

두번째 접근부터는 구글링을 통하여 풀이를 보았습니다. 

두번째 접근: 분할 정복 + 그리디

이 문제는 분할 정복과 그리디를 통해 풀이가 가능합니다. 그 이유는 모든 정육면체의 길이가 2의 지수승으로 이루어져있기 때문에 제일 큰 정육면체로 채울 수 있다면 (개수만 충분하다면) 그보다 작은 정육면체로도 채우는 것이 가능하기 때문에 그리디가 가능하고  정육면체로 박스의 한쪽을 채웠을 때 남은 부분을 직육면체 3개로 나눌 수 있기 때문에 분할 정복이 가능하게 됩니다. 

보라색 정육면체가 채워쳤을 때 파랑, 초록, 주황색의 채워야하는 직육면체가 생기게 되고 이를 채워나가면 됩니다. 각 직육면체의 사이즈에 들어가는 가장 큰 정육면체부터 채워나갔을 때 모든 직육면체를 채울 수 있으면 해당 박스는 채울 수 있고 이때 필요한 정육면체의 개수가 최소 개수가 되게 됩니다.

 

세번째 접근: 수학 + 그리디

다른 언어에서는 두번째 접근으로 풀이가 가능하지만 아쉽게도 python3와 pypy3로는 각각 시간초과가 나게 됩니다. 그래서 수학적으로 접근해서 풀이해야합니다. 두번째 접근에서 알 수 있듯이 정육면체를 최소로 쓰기 위해선 가장 큰 정육면체부터 사용해주면 됩니다. 

 

가장 큰 정육면체부터 남아있는 박스에 얼마나 채워넣을 수 있는지를 알아야합니다. 그렇게 하기 위해서는 현재 얼마나 채워져있는지를 알아야합니다. 이는 간단하게 알 수 있는데 (전체 부피에 넣을 수 있는 정육면체의 개수) - (지금까지 넣은 정육면체의 개수)를 해주면됩니다. 지금까지 넣은 정육면체의 개수는 이전까지 넣은 정육면체의 개수 X8을 해주면 되는데 그 이유는 항상 2의 지수승으로 이루어진 정육면체가 주어지게 되기 때문에 항상 부피가 8배차이가 나게 됩니다. 가지고 있는 정육면체의 개수와 남은 부피를 채우기 위해 필요한 정육면체의 개수 중에 더 작은 개수를 택해주면 됩니다.

 

정육면체로 박스를 채웠는지 아는 방법은  마지막 1 * 1 * 1의 정육면체까지 사용하여 박스를 채웠을 때 사용된 정육면체의 개수와 박스의 부피가 같으면 박스를 채운 것이고 그렇지 않으면 박스를 채우지 못한 것이 됩니다.

3. 풀이

1. 분할정복 + 그리디(파이썬에서는 시간초과 발생)

import sys, math
sys.setrecursionlimit(10 ** 5)
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

length, width, height = tuple(map(int, input().split()))
n = int(input())

size =[0] * 20
ans = 0

for _ in range(n):
    s, cnt = tuple(map(int, input().split()))
    size[s] = cnt

# print(size)

def getSize(length):
    return int(math.log2(length))

flag = False

def dq(l, w, h):
    global ans, flag
    min_length = min(l, w, h)

    if min_length == 0:
        return

    flag = False
    s = getSize(min_length)
    cur_size = 0
    for i in range(s, -1, -1):
        if size[i]:
            size[i] -= 1
            ans += 1
            flag = True
            cur_size = 1 << i
            break

    # 채울 수 있는 조각을 찾지 못한 경우
    if not flag:
        return

    dq(l - cur_size, w, h)
    dq(cur_size, w - cur_size, cur_size)
    dq(cur_size, w, h - cur_size)


dq(length, width, height)

if flag:
    print(ans)
else:
    print(-1)

 

2. 수학 + 그리디

import sys, math
#sys.setrecursionlimit(10 ** 5)
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

length, width, height = tuple(map(int, input().split()))
n = int(input())

size =[]
ans = 0

for _ in range(n):
    size.append(tuple(map(int, input().split())))

size.sort(reverse=True)


total_cnt, ans = 0, 0
for power, cnt in size:
    # 현재 크기의 정육면체를 이용해 지금까지 채운 부피
    total_cnt *= 8
    # 현재 정육면체의 한변의 길이
    cur_len = 2 ** power

    # 남은 부피를 채우기 위해 필요한 정육면체의 개수
    fill_cnt = (length // cur_len) * (width // cur_len) * (height // cur_len) - total_cnt

    # 가지고 있는 정육면체와 필요한 정육면체의 개수 중 최소를 선택한다.
    fill = min(fill_cnt, cnt)

    ans += fill
    total_cnt += fill

if total_cnt == length * width * height:
    print(ans)
else:
    print(-1)

4. 회고

접근조차 하지 못했던 굉장히 어려웠던 문제였습니다. 특히, 분할정복 + 그리디로 풀어야하는 유형의 문제는 처음 만나봐서 더 어려웠던 것 같습니다. 직육면체의 한쪽을 채웠을 때 다른 3개의 직육면체로 나눌 수 있는 아이디어는 생각치도 못했습니다.

5. 배운점

큰 문제를 작은 문제로 쪼개서 해결하는 아이디어, 그리디로 해결할 수 있는 문제인지 판단할 수 있는 근거