[백준] 1493번 - 박스채우기 (파이썬)

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

1493번: 박스 채우기

 

[코드]

import sys

length, width, height = map(int, sys.stdin.readline().split())
cube_type_num = int(input())
cubes = [0] * 20
for i in range(cube_type_num):
    t, cnt = map(int, sys.stdin.readline().split())
    cubes[t] = cnt

total_cube_cnt = 0
answer = 0

for i in range(19, -1, -1):
    total_cube_cnt = total_cube_cnt * (2 ** 3)
    l, w, h = length//2**i, width//2**i, height//2**i
    cnt = min(cubes[i], l * w * h - total_cube_cnt)

    total_cube_cnt += cnt
    answer += cnt
if total_cube_cnt == (length * width * height):
    print(answer)
else:
    print(-1)

 

구글링하면 알 수 있듯이 그리디, 분할정복으로 푸는 문제이다.

하지만 파이썬에서는 재귀적으로 풀이시 시간 또는 메모리초과가 발생하였다.

=> (참고) c++ 풀이 https://bled214.tistory.com/374

비재귀적 방식으로 푸는 풀이는 다음과 같다.

[코드 설명]

문제의 예제와 같은 값이 입력되었다 가정하자

길이가 20인 리스트를 만든다. 

이때 리스트의 인덱스는 2의 "n"승을 의미하고 해당 인덱스에 들어간 값은 큐브의 개수를 의미한다. 

예를들어 cubes[1] = 10 의 의미는 2의 1승의 변의 길이를 가진 정사각형 큐브가 10개 있다는 의미이다.

큐브의 종류는 2의 0승부터 19승 까지이므로 길이가 20인 리스트를 생성하면 된다.

그다음으로

total_cube_cnt 변수가 햇갈리지만 일단 넘어가자. answer 는 사용한 큐브개수이다.

큰 큐브부터 채워야 최대한 적게 큐브를 사용 하므로 19부터 0까지 역순으로 for 문을 돌린다.

* i 가 19인 경우를 생각해보자

l = length // 2**i 는 박스 length 길이를 2의 19승으로 나눈 몫, 다시말해 2의 19승 변을 가진 정사각형이 length 에 몇개 들어갈 수 있는지 구하는 값이다.

그렇게 h, w 를 구하여 l * h * w 를 구하면 2의 19승 변을 가진 큐브가 주어진 박스에 최대 몇개까지 들어갈 수 있는지 개수가 나온다. 

(일단 total_cube_cnt 는 0이므로 빼주는 것의 의미는 넘어가자.)

이때 실제  2의 19승 변을 가진 큐브 개수는 cubes[19] 에 있으므로  min(cubes[19],  l * h * w )  를 구해야 한다.

예제의 경우 0 이다.

* i 가 3까지는 전부 0이다

 

* i 가 2인 경우를 생각해보자

 l * h * w  = 1 * 1 * 2 = 2

cubes[2] = 1 이므로 

min(cubes[19],  l * h * w ) = 1 이다. (2의 2승의 큐브가 들어갈 수 있는 최대개수는 2개지만 주어진게 1개밖에 없으므로)

total_cube_cnt는 2의 3승 을 곱하여 8이 된다. answer 는 사용한 큐브개수이므로 1을 더한다.

* i 가 1인 경우를 생각해보자

 l * h * w  = 2 * 2 * 4 = 16 이다. 그런데 여기서 8을 빼줘야 한다. 

왜 빼줘야 할까?

변의 길이가 2의 1승인 큐브가 박스에 들어갈 수 있는 개수의 최댓값은 16개지만 이미 2의 2승의 큐브를 아까 하나 넣었다.  따라서 그걸 빼줘야 한다. 2의 2승의 큐브 1개는 2의 1승의 큐브개수로 환산하면 8개이다. ->(4*4*4) / (2*2*2) = 8

따라서 매번 루프 때마다 2의 3승씩 곱해줘야 한다. 

min(cubes[i], l * w * h - total_cube_cnt) = min(10, 8) = 8

 

* 마지막 루프 i 가 0인 경우를 생각해보자

변의길이가 1인 큐브로 넣을 수 있는 최대 개수  l * h * w  = 4 * 4 * 8 = 128,  total_cube_cnt 는 16 * 8 = 128

128 - 128 = 0 이다

박스의 길이는 자연수값이 주어지므로 변의 길이가 1인 큐브로는 반드시 빈틈없이 채워진다.

그런데 지금까지 박스에 채운 큐브의 부피를 변의길이가 1인 큐브개수로 환산하여 서로 빼면 0이 되었으므로 박스를 전부 채웠다고 말할 수 있다.

따라서 정답의 개수는 9이다.

만약에 total_cube_cnt != (length * width * height) 이면 박스를 완전히 채우지 못하였으므로 -1을 출력한다.