220526 - 박스 채우기

첫째 줄에 세 자연수 length width height가 주어진다.
둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.
셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력

첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

입출력 예

Input	Output
4 4 8 3 0 10 1 10 2 1	9
4 4 8 3 0 10 1 10 2 10	2
10 10 11 1 0 2000	1100
10 10 11 1 0 1099	-1
37 42 59 6 0 143821 1 14382 2 1438 3 143 4 14 5 1	5061

◾ 풀이

1. 해설

참고 : https://lcyking.tistory.com/8
탐욕법(그리디 알고리즘)을 활용하여 해결할 수 있다.
큰 큐브부터 차례로 사용하며 박스를 채울 수 있는지 확인한다.
- 큰 큐브로 채울 수 있는 공간은 작은 큐브로 채울 수 있다.(개수가 충분하다면!)
- 큰 큐브로 채운 공간은 작은 큐브 (큰 큐브 개수) * (2^3)개로 채울 수 있다.
- 예) 4 x 4 x 4 공간을 채우는 경우
  - 1 x 1 x 1 : 64개 필요
  - 2 x 2 x 2 : 8개 필요
  - 4 x 4 x 4 : 1개 필요
- [각 큐브로 채울 수 있는 최대 공간] - [이전 큐브로 채운 공간]을 통해 계산해 나간다.
- 큐브로 채울 수 있는 공간이 전체 공간보다 작다면 불가능한 경우이다.

2. 프로그램

length, width, height 입력
n, cube 입력
answer, before 초기화
큰 큐브부터 차례로 채울 수 있는 공간 확인
- before 8 | before (2 ** 3) | before << 3
- max_cnt 계산 : min(현재 큐브로 채울 수 있는 최대 공간, 큐브의 개수)
- answer, before 업데이트
before, 전체 박스(length width height) 비교
- 같은 경우 : answer 출력(최소 큐브 개수)
- 작은 경우 : -1 출력(불가능한 경우)

# 코드
length, width, height = map(int, input().split())
n = int(input())
cube_cnt = {}
for _ in range(n):
    a, b = map(int, input().split())
    a = 2 ** a
    cube_cnt[a] = b

answer = 0
before = 0
for v, cnt in sorted(cube_cnt.items(), key=lambda x : -x[0]):
    before *= 8
    max_cnt = (length//v) * (width//v) * (height//v) - before
    max_cnt = min(cnt, max_cnt)
    answer += max_cnt
    before += max_cnt

if before == (length * width * height):
    print(answer)
else:
    print('-1')