[Gold III] 박스 채우기 - 1493 (그리디)

[Gold III] 박스 채우기 - 1493

문제 링크

성능 요약

메모리: 113112 KB, 시간: 124 ms

분류

분할 정복(divide_and_conquer), 그리디 알고리즘(greedy), 수학(math)

문제 설명

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력

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

풀이방법

필요한 큐브 개수의 최솟값을 출력해야한다.

단, 입력받은 상자는 정육면체가 아니지만 큐브는 무조건 정육면체 이므로, 가장 큰 큐브부터 상자에 넣어준다면, 최솟값을 구할 수 있다는 것을 유추해낼 수 있다. 즉, 그리디 알고리즘이 적용된다는 뜻.

이 문제를 풀기위해 반복적으로 수행되는 로직을 찾기위해 한, 1부터 4 x 4 x 4 정육면체까지 그려본다면 각 정육면체 당 몇 개의 큐브가 동일하게 들어가는지 알 수 있다.

1 x 1 x 1 =

2 x 2 x 2 = 1x1x1이 8개 들어감.

4 x 4 x 4 => 2x2x2가 8개 들어감.

 

그리고 한 상자에 선택된 큐브가 몇 개 들어가는지 계산하기 위해 예시를 들어본다.

예를 들어, 8 x 4 x 4에는 4 x 4 x 4가 2개가 들어간다.

이것을 수식으로 나타낸다면, 

8 * 4 * 4 => x * y * z

4 * 4 * 4 => i * i * i

라고 가정했을 때, 채우기 위한 필요한 개수는 ( x // i ) * ( y // i ) * ( z // i )  즉, 2 * 1 * 1 = 2개가 된다.

 

이렇게 두 가지의 예시를 통해 문제를 해결하기 위한 두 가지 방법을 찾을 수 있다.

첫 번째). 한 단계 큰 정육면체 부피를 모두 채우려면 8개의 큐브가 들어간다.

두 번째). 현재 큐브로 상자를 채우기 위해 필요한 개수를 수식으로 나타낼 수 있다.  ( x // i ) * ( y // i ) * ( z // i )

이 두가지 방법을 이용하여 문제를 해결할 수 있다.

- 풀이 순서

1. 입력받은 큐브들을 내림차순으로 정렬한다. ( 그리디 알고리즘으로, 가장 큰 큐브부터 상자에 넣기 위해)

2. 각 큐브를 하나씩 방문한다.

3. 2번을 수행하면서 매 번 현재까지 채운 정육면체 부피를 기록한다 ( total *= 8 : 8을 곱하는 이유는 위에 언급한 첫 번째 이유 때문.)

4. 현재 공간에 채울 수 있는 개수에서 지금까지 채운 개수를 빼준다. ( ( x // i ) * ( y // i ) * ( z // i ) - total)

5. 4번으로 인해 해당 큐브로 상자에 넣을 수 있는 개수(fill)를 구할 수 있다. 그러나, 큐브당 주어진 개수(cnt)가 존재하므로 그 개수만큼만 넣어준다.

6. 2~5번을 모든 큐브를 방문할 때까지 반복한다.

7.깔끔하게 전체 부피를 다 채웠다면 (total == vol) 현재까지 사용한 개수(result)를 출력한다. 아니라면 -1 출력

import sys
input = sys.stdin.readline

x, y, z = map(int,input().split())
vol = x * y * z # 전체 부피
n = int(input())

cube = [list(map(int,input().split())) for _ in range(n)]
cube.sort(reverse=True) # 제일 큰 정육면체부터

result = 0 # 필요 큐브 개수
total = 0 # 총 채운 부피

for idx, cnt in cube:
    total *= 8 # 이전 정육면체 부피의 1/8
    square = 2 ** idx # 2**i 정육면체

    # 현재 공간에 채울 수 있는 개수 - 지금까지 채운 개수
    fill = (x // square) * (y // square) * (z // square) - total
    fill = min(cnt, fill) # 실제로 채우기 가능한 개수

    result += fill
    total += fill

if total == vol:
    print(result)
else:
    print(-1)