https://www.acmicpc.net/problem/1092
접근
- 크레인과 박스를 내림차순 정렬한다.
- 첫 번째 크레인이 첫 번째 박스를 옮길 수 없으면 -1을 출력한다.
- 두 번째 크레인부터 순회하면서 박스를 옮길 수 있는지 확인한다.
- 박스를 옮길 수 있는 크레인 중에서 가장 적게 옮긴 크레인이 박스를 옮긴다.
- 박스를 옮길 수 있는 크레인이 없거나 가장 적게 옮긴 크레인이 첫 번째 크레인이면 첫 번째 크레인이 박스를 옮긴다.
풀이
from sys import stdin
from collections import deque
n = int(stdin.readline())
crane = sorted(list(map(int, stdin.readline().split())), reverse=True) # (1)
_ = int(stdin.readline())
box = deque(sorted(map(int, stdin.readline().split()), reverse=True)) # (2)
if box[0] > crane[0]:
print(-1)
exit()
batch_crane = [0] * n # (3)
while box:
b = box.popleft()
worker, min_batch = 0, batch_crane[0]
for i in range(1, n): # (4)
if crane[i] >= b: # (5)
if batch_crane[i] < min_batch:
worker = i
min_batch = batch_crane[i]
else:
break
batch_crane[worker] += 1
print(max(batch_crane))
- (1) 크레인의 무게 제한을 내림차순 정렬한다.
- (2) 박스의 무게를 내림차순 정렬한다.
- (3) 각 크레인마다 박스를 옮긴 개수이다. 모든 크레인은 동시에 움직이기 때문에 박스를 옮긴 개수가 최대한 균일해야 한다.
- (4) 두 번째 크레인부터 순회한다. 크레인을 내림차순 정렬했기 때문에 두 번째 크레인에서 else문을 만나면 첫 번째 크레인이 박스를 옮긴다.
- (5) i번째 크레인이 박스를 옮길 수 있을 때 옮긴 개수가 가장 적으면 박스를 옮길 대상이 된다.