백준 1092번 : 배 in Python

1092번: 배

 

www.acmicpc.net

이 문제는 무게 제한이 서로 다른 N개의 크레인이 무게가 서로 다른 M개의 박스를 배에 싣는데 걸리는 최소 시간을 구하는 문제이다.

이를 해결하기 위해서는 되도록이면 각 크레인이 자기 자신의 무게 제한에 최대한 가까운 박스를 옮기도록 해야 한다. 왜냐하면 무게 제한에 가까운 박스부터 먼저 옮겨야 나중에 남은 박스는 무게가 작은 것만 남아 거의 모든 크레인이 옮길 수 있어 시간을 절약할 수 있기 때문이다.

그러므로 주어진 크레인의 무게 제한과 각 박스의 무게를 내림차순으로 정렬한다. 그리고 단위 시간마다 무게 제한이 큰 크레인부터 옮길 박스를 할당하는데, 이때 무게가 무거운 박스부터 살펴보면서 무게 제한보다 작은 박스가 나오면 해당 크레인에 박스를 할당한 뒤 다음 크레인으로 넘어간다. 이러한 방식으로 모든 크레인에 박스를 할당하면 배에 박스들을 옮기고 다시 위 과정을 모든 박스를 옮길 때까지 반복한다. 그러면 모든 박스를 옮기기 위한 최소 시간을 구할 수 있다.

단, 만약 박스들의 무게의 최댓값이 크레인의 무게 제한의 최댓값보다 더 큰 경우에는 어떤 크레인으로도 최대 무게의 박스를 옮길 수 없으므로 -1을 출력한다.

이를 코드로 구현하면 다음과 같다.

import heapq
N = int(input())
cranes = list(map(int, input().split()))
M = int(input())
freights = list(map(int, input().split()))
# 무게 제한이 큰 크레인, 무거운 박스부터 살펴보기 위해 내림차순으로 정렬한다.
cranes.sort(reverse=True)
freights.sort(reverse=True)
# 각 박스를 배로 옮겼는지를 나타내는 배열
check = [0 for _ in range(M)]
# 배로 옮긴 박스의 갯수
cnt = 0
# 모든 박스를 배로 옮기는데 걸리는 최소시간
res = 0
# 만약 모든 크레인의 무게 제한보다 더 무거운 박스가 있으면 해당 박스를 배로 못 옮기므로 -1을 출력한다. 
if cranes[0] < freights[0]:
    print(-1)
else:
    # 모든 박스를 배로 옮길 때까지
    while cnt < M:
        res += 1
        # 몇 번째 박스까지 보았는지를 나타내는 변수
        j = 0
        # 각 크레인마다 박스를 할당한다.
        for i in range(N):
            # 모든 박스를 다 살펴볼 때까지
            while j < M:
                # 해당 박스를 아직 배로 옮기지 않았고 현재 크레인이 옮길 수 있는 박스라면
                if check[j] == 0 and cranes[i] >= freights[j]:
                    # 해당 박스를 배로 옮긴 뒤 다음 크레인으로 넘어가 그 다음 박스부터 살펴본다.
                    check[j] = 1
                    cnt += 1
                    j += 1
                    break
                j += 1
    print(res)