해당 문제에서는 정육면체를 가장 최소화해서 사용하기 위해는 가장 큰 정육면체부터 사용하면 됩니다. 그 이유는 돈을 거슬러 줄 때 동전과 지폐의 수를 최소화하면서 거슬러주는 원리와 같습니다. 각 정육면체의 한 변의 길이는 2^i라는 규칙을 가지고 있기 때문에, 큰 정육면체는 다른 작은 정육면체로 구성 가능하기 때문에 가장 큰 정육면체부터 사용하는 그리디 접근이 가능합니다.
만약 어떤 정육면체를 채웠다면, 나머지 부분 또한 동일한 타입의 작은 문제로 생각할 수 있습니다.
일반화 해보면, 예를 들어 현재 (l,w,h)의 상자가 있을 때 이를 한 변의 길이가 x인 정육면체로 채우면, 나머지 상자를 (l-x,x,x), (x,w-b,x), (l-x,w-x,x), (l,w,h-x) 크기를 가진 4개의 상자를 채우는 하위 문제로 바꿀 수 있습니다.
하지만 해당 문제는 다른 언어는 문제가 없지만 파이썬은 분할정복으로 풀 수 없습니다. 재귀 깊이 문제와 메모리 초과가 나기 때문인데, 이건 파이썬 언어 종특이라.. 쩔 수 없이 다른 방법으로 풀어야 합니다.
먼저 분할정복을 이용한 코드는 다음과 같습니다. 분할정복으로 문제를 풀 때 가장 중요한 것은 기저 사건을 설정하는 것입니다. (즉, 언제 재귀를 종료할지!)
'''
2024 02 12
박스 채우기
골2
분할정복
'''
import sys
sys.setrecursionlimit(1000000)
L, W, H = map(int, sys.stdin.readline().strip().split(' '))
N = int(sys.stdin.readline())
CUBE = [list(map(int, sys.stdin.readline().strip().split(' '))) for _ in range(N)]
ret = 0
def solve(l, w, h):
global ret
if l == 0 or w == 0 or h == 0: # 기저 사건
return True
for i in range(len(CUBE) - 1, -1, -1):
cur = 1 << CUBE[i][0]
count = CUBE[i][1]
if count > 0 and l >= cur and w >= cur and h >= cur:
ret += 1
CUBE[i][1] -= 1
# Divide & Conquer
a = solve(l - cur, cur, cur)
b = solve(cur, w - cur, cur)
c = solve(l - cur, w - cur, cur)
d = solve(l, w, h - cur)
# Merge
return (a and b and c and d)
return False # CUBE를 모두 순회 했지만 채울 수 없다는 의미
if solve(L, W, H):
print(ret)
else:
print(-1)
다른 풀이는 수학적으로 접근해야하는데,
해당 풀이는 좀 더 고민해보고 작성해보겠습니다
