[BaekJoon] 1092번 배 (Python) 문제 풀이 [Gold 5]

문제

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

 

어떻게 풀 것인가?

그리디 + 정렬 문제입니다.

핵심 아이디어는 가장 무거운 짐을 가장 능력이 좋은 크레인에 배정하는 것입니다. 매 라운드(1분)마다 각 크레인이 들 수 있는 박스 중 가장 무거운 것을 선택하면 전체 시간을 최소화할 수 있습니다.

 

크레인은 내림차순, 박스는 오름차순으로 정렬해둡니다. 그러면 각 크레인마다 bisect_right로 자신이 들 수 있는 가장 무거운 박스의 인덱스를 빠르게 찾을 수 있습니다.

 

해당 박스를 리스트에서 제거하고, 모든 박스가 사라질 때까지 반복하면서 라운드 수를 세면 됩니다.

가장 큰 크레인의 무게 제한보다 무거운 박스가 있으면 옮길 수 없으므로 -1을 출력합니다.

 

코드

import sys
from bisect import bisect_right
input = sys.stdin.readline

N = int(input())
cranes = list(map(int, input().split()))
M = int(input())
freight = list(map(int, input().split()))

cranes.sort(reverse=True)
freight.sort()

count = 0
if cranes[0] < freight[-1]:
    print(-1)
else:
    while freight:
        for crane in cranes:
            if not freight:
                break
            idx = bisect_right(freight, crane) - 1
            if idx >= 0:
                freight.pop(idx)
        count += 1
    print(count)