배

알고리즘 구분 : 그리디, 정렬

문제 풀이 : 문제의 특징은 크레인은 1분에 박스를 하나씩 배에 실을 수 있다는 것과 모든 크레인은 동시에 움직일 수 있다는 것이다. 주의해야할 점은 두 개의 크레인으로 한 개의 박스를 같이 옮기는 행위는 불가능하다는 점이다.
첫 번째로, 크레인의 무게 제한과 박스의 무게를 내림차순으로 정렬을 진행하였다.
내림차순으로 정렬을 진행해야하는 이유 : 정렬 후, 배열의 맨 앞부터 옮기는 연산을 진행하게 될텐데, 오름차순으로 정렬하여 가벼운 박스를 먼저 옮기다 무거운 박스가 남았을 경우, 일부 크레인은 옮기는 행동에 제약이 걸릴 수 있고, 이는 최솟값을 구하려는 과정과 맞지 않다고 판단하였기 때문이다.
이후, 크레인의 무게 제한 중 최대보다 박스 중 가장 무거운 무게가 더 클 경우, 크레인으로 옮길 수 없으면 -1을 출력하라는 문제의 안내에 맞게, 옮기는 과정을 진행하기 전에 조건문을 통해 옮길 수 없는 무게가 존재하는지 확인할 수 있도록 하였다.
크레인을 움직이는 과정에서 박스를 지우지 않고 계속 반복문을 돌리게 된다면, 시간 초과가 발생하기에 del box[j]를 통하여 이미 옮긴 박스는 리스트에서 제거하도록 구현하였다.

소스 코드 :

import sys

# 크레인 수와 크레인의 제한 무게 입력
n = int(sys.stdin.readline())
crane = list(map(int, sys.stdin.readline().split()))
crane.sort(reverse = True)

# 박스 수와 박스의 무게 입력
m = int(sys.stdin.readline())
box = list(map(int, sys.stdin.readline().split()))
box.sort(reverse = True)

# 크레인이 박스 무게를 들지 못할 경우, -1 출력
if crane[0] < box[0]:
        print(-1)
else:
    # 크레인 움직이는 과정
    time = 0
    while True:
        if n < len(box):
            cnt = n
        else:
            cnt = len(box)
        
        for i in range(cnt):
            for j in range(len(box)):
                if crane[i] >= box[j]:
                    del box[j]
                    break
        time += 1
    
        if box == []:
            print(time)
            break

• 문제 출처 : https://www.acmicpc.net/problem/1092
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.