문제 링크

<aside> 💡 그리디 알고리즘/정렬

</aside>

Memory 115412KB Time 128ms Code Length 728B

import sys
input = sys.stdin.readline
N = int(input())
cranes = list(map(int, input().split()))
M = int(sys.stdin.readline())
boxes = list(map(int, input().split()))

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

if max(cranes) < max(boxes):
    print(-1)
    sys.exit()

positions = [0] * N 
checked = [False] * M

result = 0
count = 0

while True:
    if count == len(boxes):
        break
    for i in range(N):
        while positions[i] < len(boxes):
            if not checked[positions[i]] and cranes[i] >= boxes[positions[i]]:
                checked[positions[i]] = True
                positions[i] += 1
                count += 1
                break
            positions[i] += 1
    result += 1
print(result)

이 코드는 크레인과 박스를 이용한 물품 이동 최소 시간을 계산하는 코드이다.

먼저, 크레인과 박스의 수를 입력받고, 각 크레인이 들 수 있는 무게와 박스의 무게를 입력받는다. 크레인과 박스의 무게는 내림차순으로 정렬한다.

만약 가장 무거운 박스의 무게가 가장 무게를 많이 들 수 있는 크레인의 무게보다 무거우면, 모든 박스를 옮길 수 없으므로 -1을 출력하고 프로그램을 종료한다.

그렇지 않은 경우, 각 크레인이 현재 옮기고 있는 박스의 위치를 나타내는 positions 배열과 각 박스가 이미 옮겨졌는지 여부를 나타내는 checked 배열을 초기화한다.

while문을 통해 모든 박스가 옮겨질 때까지 반복한다. 각 크레인은 자신이 옮길 수 있는 가장 무거운 박스를 찾아 옮긴다. 만약 크레인이 옮길 수 있는 박스를 찾으면, 그 박스를 옮겼다는 표시를 하고 다음 박스로 넘어간다.

모든 크레인이 한 번씩 움직일 때마다 시간을 1씩 증가시킨다. 모든 박스가 옮겨지면 그동안 증가시킨 시간을 출력한다.