[백준] 1092번 배

💡문제접근

• 처음엔 오름차순으로 정렬해서 문제를 해결하려고 시도했으나 계속 WA를 받아서 결국 포기하고 질문게시판에 있는 방법인 내림차순으로 정렬해서 해결하는 방법을 시도했다.

• [오름차순 접근에 대한 질문] 질문게시판 내용

💡반례

입력

2
1 2
4
1 1 2 2

• 가벼운 박스부터 매달게 된다면 남은 박스는 2 2가 된다. 이렇게 된다면 견딜 수 있는 하중이 1인 크레인은 아무런 작업도 할 수 없게 되는 것이고 견딜 수 있는 하중이 2인 크레인이 2번에 걸쳐 작업을 수행하게 된다. 이렇게 되면 모든 박스를 배로 옮기는데 소요되는 시간은 3이 나온다.

• 오름차순으로 작업을 수행한다면 모든 크레인이 모두 열심히 작업을 수행할 수 있지만 시간이 지나면 점점 무거운 박스들을 옮겨야 하는데 이 때 가벼운 크레인들은 작업을 수행할 수 없어 무거운 크레인들만 계속 일을 하게 된다. 따라서 오름차순으로 작업을 수행하게 된다면 시간대비 작업효율이 좋지 못하므로 내림차순으로 작업을 수행해야 시간대비 작업효율이 우수하다.

💡코드(메모리 : 115248KB, 시간 : 4008ms)

import sys
input = sys.stdin.readline

N = int(input().strip())
weight_limit = list(map(int, input().strip().split()))
M = int(input().strip())
box = list(map(int, input().strip().split()))

weight_limit.sort(reverse=True)
box.sort(reverse=True)

time = 0
if max(box) > max(weight_limit):
    print(-1)
    sys.exit(0)
while True:
    if len(box) == 0:
        break
    time += 1
    for i in weight_limit:
        for j in range(len(box)):
            if i >= box[j]:
                box.remove(box[j])
                break
print(time)

💡소요시간 : 41m