[코딩테스트][백준] 🔥 백준 1493번 "박스 채우기" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 2시간

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

n=int(input())
cubes=[]

for i in range(n):
    type,cnt=map(int,input().split())
    cubes.append([type,cnt])

cubes.sort()

fail=False
answer=0
prevVolume=length*width*height
prevL=1

for i in range(n):
    L=2**cubes[i][0]
    
    nLength=length//(L/prevL)
    nWidth=width//(L/prevL)
    nHeight=height//(L/prevL)
    
    nVolume=(nLength*nWidth*nHeight)*(L**3)
    
    if cubes and (prevVolume-nVolume)//(prevL**3)>cubes[i-1][1]:
        lastVolume=prevVolume-nVolume
        index=i-1
        while lastVolume>0 and index>=0:
            nLen=cubes[index][0]
            target=((2**nLen)**3)*cubes[index][1]
            if target>=lastVolume:
                k=lastVolume//((2**nLen)**3)
                cubes[index][1]-=k
                answer+=k
                lastVolume=0
                break
            else:
                answer+=cubes[index][1]
                cubes[index][1]=0
                lastVolume-=target
                index-=1
        if lastVolume>0:
            fail=True
            break
    elif cubes:
        cubes[i-1][1]-=(prevVolume-nVolume)//(prevL**3)
        answer+=(prevVolume-nVolume)//(prevL**3)
    if i==n-1:
        if nLength*nWidth*nHeight>cubes[i][1]:
            lastVolume=(nLength*nWidth*nHeight-cubes[i][1])*(L**3)
            answer+=cubes[i][1]
            index=i-1
            while lastVolume>0 and index>=0:
                nLen=cubes[index][0]
                target=((2**nLen)**3)*cubes[index][1]
                if target>=lastVolume:
                    answer+=lastVolume//((2**nLen)**3)
                    lastVolume=0
                    break
                else:
                    answer+=cubes[index][1]
                    lastVolume-=target
                    index-=1
            if lastVolume>0:
                fail=True
            break
        else:
            answer+=nLength*nWidth*nHeight
            break
    prevVolume=(nLength*nWidth*nHeight)*(L**3)
    length,width,height=nLength,nWidth,nHeight
    prevL=L

if fail:
    print(-1)
else:
    print(int(answer))

박스 채우기: 큐브로 공간 최적화하기! 📦🧊

박스를 주어진 큐브를 사용해서 채우는 문제이다. 이 때 박스의 가로, 세로, 높이가 주어지며 큐브는 정육면체이며, 한 변의 길이가 2의 제곱꼴이다.

처음에는 큐브를 큰거부터 채우면 되지 않을까 하다가 그러면 남은 공간을 채울 방법이 없거나 최소가 안되지 않을까라는 생각이 들어서 역으로 치환하면서 풀었다. 즉 먼저 제일 작은 큐브인 1x1x1인 큐브로 다 채우고 나서 크기가 큰 큐브 순으로 바꾸는 것이다. 그렇게 되면 반드시 전부 채울 수 있는 방향성을 가지고 채울 수 있다고 생각하였다.

바로 위의 큐브로 치환을 한다면 우리는 갯수를 구하는 것이기에 현재의 한 변의 길이에서 전의 정육면체의 길이만큼만 나눠주면 된다. 예를 들어 2x2x2로 나누어서 10x10x11개라면 4x4x4로 치환할 때, 5x5x5개가 되는 것이다. 그리고 남은 부피는 그 전단계로 무조건적으로 나누어질 수 있다. 왜냐하면 단계별로 치환이 되기 때문이다. 그렇기 때문에 (2x2x2)x(10x10x11)-(4x4x4)x(5x5x5)가 남는 부피가 되고 이 부피는 (2x2x2)로 반드시 나누어진다. 그만큼 사용하면 되는 것이다. 만약 갯수가 부족하다면 남은 부피는 반드시 단계별로 치환해왔기 때문에 다시 단계의 역으로 내려가면서 갯수로 치환이 가능하다. 그렇기 때문에 이를 반영하면 된다.

마지막 단계까지 갔을 때에는 남은 부피를 치환하는 것뿐만 아니라 현재 각 변을 나누어 나온 갯수가 그대로 사용되는 것이기 때문에 이를 더해주어야 한다. 이 처럼 풀면 원하는대로 치환해서 푸는 그리디처럼 풀 수 있다.

이렇게 Python으로 백준의 "박스 채우기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊