백준 1092 - 배 (파이썬)

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

풀이

크레인을 이용해서 박스를 옮기는 문제이다.

각 크레인은 특정한 무게까지의 박스를 들 수 있으며, 최소 시간 내에 모든 바스를 옮기는 것이 목표이다.

먼저 A, B 를 입력 받고, 각 박스를 각각 내림차순으로 정렬하여, 가장 무거운 박스를 가장 무거운 크레인부터 배치할 수 있도록 변경한다.

if A[0] < B[0] :
    print(-1)
    exit()

그리고 만약 가장 강한 크레인이 가장 무거운 박스를 들 수 없다면, 모든 박스를 옮기는 것이 불가능 하므로, -1을 출력한다.

count = 0

while len(B) > 0 :
    for a in A :
        if len(B) > 0 and a < B[-1] :
            break

        for b in B :
            if b <= a :
                B.remove(b)
                break
    count += 1

각 크레인은 들 수 있는 가장 무거운 박스를 찾고 제거한다.

그리고 모든 크레인이 한 번씩 돌고 나면 1분이 경과한 것으로 간주하다.

박스가 없어질때까지 반복하고, 모든 박스를 옮기는 데 걸린 최소 시간을 출력하면 된다.

시간 복잡도 분석

1. 정렬 → O(N log N) + O(M log M)
2. 반복문 → 최악의 경우 O(N * M)

즉, O(N log N) + O(M log M) + O(NM)

코드

# 백준 1092 - 배
# 분류 : 그리디

N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)

if A[0] < B[0] :
    print(-1)
    exit()

count = 0

while len(B) > 0 :
    for a in A :
        if len(B) > 0 and a < B[-1] :
            break

        for b in B :
            if b <= a :
                B.remove(b)
                break
    count += 1

print(count)