백준 1493 박스 채우기 (파이썬)

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

1493번: 박스 채우기

풀이

직사각형 박스에 주어진 정육면체 큐브들을 채워넣는 문제입니다. 처음 문제를 접하였을때 부피로 어떻게든 풀어야 겠다고 생각은 하였지만 어떻게 해결을 해야할지 고민을 하였지만 구현을 하기 까다로운 문제였다고 생각합니다.

제가 처음 접근한 방식은 주어진 상자에 주어진 큐브들을 정해진 갯수만큼 채워넣고 남은 부피를 갱신시켜 가며 풀고자 하였지만 구현으로 옮길 자신이 없어 결국 다른 사람의 풀이를 보았습니다.

(참고한 블로그 글)

 

대체로 접근 방식은 비슷하였으나 남은 부피를 갱신하며 풀이를 진행하려는 저의 방법과는 달리 해당 글에서는 큐브 인덱스마다 큐브의 갯수를 구하는 방식으로 접근하였습니다.

참고한 블로그 글에서 이미 정리가 잘 되어 있지만 다시 한번 더 설명 글을 남기자면 아래와 같습니다.

 

1. 문제로 부터 주어진 큐브의 인덱스, 큐브의 개수를 리스트에 저장해놓고 내림차순으로 정렬해 부피가 큰 큐브부터 비교할 수 있도록 만듭니다.
2. 문제의 정답인 상자를 채우는데 들어간 큐브의 개수를 저장하는 answer와 지금까지 상자를 채우는데 사용한 큐브의 개수를 반복문에서 사용하는 큐브의 개수로 변환하는데 사용할때 사용하는 total_cube를 생성합니다.
3. 내림차순으로 정렬된 큐브들의 리스트의 원소들(큐브의 인덱스, 큐브의 갯수)을 반복문을 통해 뽑아냅니다.
4. 이전 크기의 큐브의 개수를 현재 뽑아낸 큐브의 개수로 변환합니다.
   1. 이때 8을 곱하는 이유는 이전에 사용한 큐브 하나의 부피는 현재 사용할 큐브 하나의 부피보다 8배 더 크기 때문입니다.
      • ex) 이전에 사용한 큐브의 한변의 길이를 2x2x2라고 하였을때 해당 큐브의 부피는 8이고 현재 반복문에서 사용할 큐브의 한변의 길이는 1x1x1이고 해당 큐브의 부피는 1이기 때문입니다.
      • 그리고 만약 한변의 길이가 2x2x2인 큐브 하나를 박스를 채우는데 사용하였다면 이는 1x1x1인 큐브를 8개 사용한것과 동일하기 때문입니다.
5. 해당 큐브의 길이를 기반으로 큐브의 부피를 구하고, 남아있는 부피에 해당 큐브를 몇개 넣을수 있는지 확인합니다.
6. 문제에서 주어진 큐브의 개수와 직접 계산한 넣을수 있는 큐브의 개수를 서로 비교해 최소값을 total_cube와 answer에 저장합니다.
   1. 이때 저는 5번에서 구한 값이 음수가 될수도 있다고 생각하여 조건문을 통해 양수일 경우에만 값을 업데이트 할 수 있다고 문제를 풀었습니다. (이 부분은 확실치 않으니 혹시 다른 의견이 있으시면 댓글로 알려주세요)

글로 풀어쓰니 복잡해보이지만 풀이 코드는 상당히 짧으므로 이해하는데 어려우시지는 않으리라 생각듭니다.

코드

import sys
input = lambda: sys.stdin.readline().rstrip()

length, width, height = map(int, input().split(" "))
volume = length*width*height
numberOfCube = int(input())
cubes = [list(map(int, input().split())) for _ in range(numberOfCube)]
cubes.sort(reverse = True)

answer, total_cube = 0, 0

for cube_idx, cube_cnt in cubes:
    total_cube *= 8
    lengthOfCube = 2**cube_idx
    available_cube = (length//lengthOfCube) * (width//lengthOfCube) * (height//lengthOfCube) - total_cube

    available_cube = min(available_cube, cube_cnt)
    if available_cube > 0:
        answer += available_cube
        total_cube += available_cube

if total_cube == volume:
    print(answer)
else:
    print(-1)