백준 1493:박스채우기 [Python 파이썬 / 그리디 알고리즘]

백준 1493: 박스채우기

개킹받는 문제
발상의 전환에 실패해서 골드2 문제보다 힘들게 풀었다

2^i 길이를 한 변으로 갖는 여러 가지 정육면체로
length X width X height의 부피를 갖는 박스를 채울 정육면체의 최소 개수를 구하기

0. 주어지는 박스는 정육면체가 아닌 직육면체다 보니 처음에는 머리가 복잡해졌다. 그래서 참고한 것이 분할 정복 알고리즘.. 일단은 가능한 큰 정육면체로 채우고 남은 빈 자리를 세 부분의 직육면체로 나누어 재귀 함수를 실행하는 것이다.

1. 그래서 많은 C++ 코더분들이 활용한 분할정복 알고리즘에 맞춰 풀어보려 했으나 파이썬 종특인지 자꾸 시간초과, 메모리 초과가 떠서 포기했다.

2. 또 다른 분들의 풀이를 참고하니 굳이 재귀 함수를 쓸 필요 없이 전체 부피에서 특정 정육면체로 가능한 최대로 채울 수 있는 개수를 세고 기록해둔 후, 한 단계 아래 정육면체에서 최대한 채울 수 있는 개수를 또 세고 전에 채운 개수를 차감하는 방법이 있었다.

3. 이 방법에서는 이전까지 채운 큐브의 개수에 8을 곱해주는 과정이 포함되어 있었는데 처음에는 왜 그렇게 하는지 머리로 받아들이지를 못하다가 각 큐브의 부피가 8배씩 차이나기 때문에 필요한 과정이라는 것을 이해하였다.

설명이 개발새발인데 아래 코드를 보면서 다시 이해해보자.

import sys
input = sys.stdin.readline


length, width, height = map(int, input().split())
total = length * width * height
N = int(input())
cube = [tuple(map(int, input().split())) for _ in range(N)]
cube.sort(reverse=True)

answer, total_now = 0, 0
for c_idx, c_cnt in cube:
    total_now *= 8 # 다음 순서 = 이전 정육면체 부피의 1/8이므로 이전까지의 개수에 8을 곱해줌 (예 : 4*4*4 1개 = 2*2*2 8개)
    c_len = 2**c_idx
    
    cnt_limit = (length // c_len) * (width // c_len) * (height // c_len) - total_now # 현재 공간에 채울 수 있는 개수 - 지금까지 채운 개수
    cnt_limit = min(c_cnt, cnt_limit) # 실제로 채우기 가능한 개수
    
    answer += cnt_limit
    total_now += cnt_limit

if total_now == total:
    print(answer)
else:
    print(-1)

1. 우선 정육면체의 정보를 cube라는 리스트 변수에 저장하였다.
   그리고 큰 정육면체부터 공간에 채워넣어야 그리디한 결과를 낼 수 있기에 sort() 함수로 리스트를 내림차순으로 정렬하였다.

2. 그 아래의 for문은 백준에서 주어준 예시가 처리되는 과정으로 이해해보도록 하겠다.

4 4 8
3
0 10
1 10
2 1

가 입력된 예시이다.

2-1. 우선 첫 iteration에서 total_now에 8을 곱해주는 과정은 total_now가 0이므로 의미가 없다.

2-2. 가로, 세로, 높이를 현재 iteration의 정육면체 한 변의 길이로 각각 나누어 곱한다. 그러면 현재 정육면체로 채울 수 있는 최대한의 개수를 얻을 수 있다. 예시를 기준으로 말하면
(4 / 4) X (4 / 4) X (8 / 4) = 2
2개를 채울 수 있게 된다. 하지만 예시에서 주어진 4X4X4 정육면체는 1개 이므로 1개만 채운다고 기록해둔다.

2-3. 이제 다음 iteration으로 넘어가면 이번에는 2X2X2의 정육면체이다. 이전 iteration에서 4X4X4 정육면체 1개를 채웠다고 기록해두었는데, 4X4X4 1개는 2X2X2 8개와 부피가 같기 때문에 2X2X2 정육면체와 비교하려면 이것에 8을 곱해주어야 한다.

2-4. 그래서 total_now가 1에서 8이 되고, 이전 iteration과 똑같이 전체 부피에 2X2X2로 채울 수 있는 최대한의 개수를 계산한다. 예제에 따르면 (4 / 2) X (4 / 2) X (8 / 2) = 16개이다. 그런데 이전 iteration에서 4X4X4 정육면체 1개, 즉 2X2X2 정육면체 8개를 이미 채워뒀다고 기록해둔 상태이므로, 추가로 채울 수 있는 2X2X2 정육면체의 개수는 16 - 8 = 8개가 최대이다.

2-5. 그리고 현재 가지고 있는 2X2X2 정육면체의 개수는 10개이므로 당연히 8개를 채울 수 있다. 그래서 8개를 더 채웠다는 의미로 total_now에 8을 더해준다. 그래서 total_now = 16이 된다.

2-6. 이제 마지막으로 1X1X1 정육면체로 채울 수 있는 개수를 세야한다. (사실 이미 공간이 다 찬 상태지만 일단은 진행한다) 이전까지 2X2X2 정육면체 16개를 채웠으므로 이것에 8을 곱하여 1X1X1 정육면체로 변환한다. 즉 16 X 8 = 128개, 그리고 박스의 전체 부피는 4 X 4 X 8 = 128이다. 1X1X1 정육면체로 채우면 당연히 부피값만큼 들어가지는데 이미 128개를 채웠다. 즉 128 - 128 = 0이기 때문에 더이상 채울 수 있는 자리가 없다.

2-7. iteration이 종료되고 total 변수와 total_now 변수가 같은지 확인한다. 같으면 answer 변수에 기록해두었던 정육면체 개수를 print하여 정답처리.