[백준] 배

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

1092번: 배

 

시간초과를 방지하기 위해서 크레인을 두 번째 이상 돌릴 때는 정렬된 박스들의 위치를 기억해서 무게 제한보다 무거운 박스인지는 비교하지 않도록 하였다.

 

cranes = [9, 8, 6], boxes = [2, 2, 4, 5, 7] 이라고 가정했을 때,

bisect_right 를 이용하여 positions = {9 : 5, 8 : 5, 6 : 4} 즉, 크레인 9번은 1 ~ 5번, 6번은 1 ~ 3번을 옮기는 경우만 생각하면 된다.

 

크레인의 무게 제한이 큰 것부터 차례대로 해당 위치에 있는 박스를 옮겼을 때, checked 배열을 만들어 옮긴 박스의 번호를 검사해주고 count 를 1 씩 더한다. 옮기지 못하는 경우를 대비하여 for 문을 positions[crane] 번까지 돌리며 두 번째부터는 이미 옮긴 박스를 비교하지 않기 위해서 positions[crane] 를 -1 씩 더해준다. count = M(모든 박스를 옮겼을 때) answer(모든 크레인이 동시에 박스를 배에 실은 횟수)를 반환한다.

 

무게 제한이 가장 큰 크레인이 옮길 수 없는 박스가 존재한다면 -1 을 반환한다. 

 

import sys
from bisect import bisect_right

N = int(sys.stdin.readline())
cranes = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
boxes = list(map(int, sys.stdin.readline().split()))
cranes.sort(reverse=True)
boxes.sort()

if cranes[0] < boxes[-1]:
    print(-1)
else:
    positions = dict(zip(cranes, [bisect_right(boxes, crane) for crane in cranes]))
    checked = [0] * M
    count = 0
    answer = 0
    
    while count < M:
        
        for crane in cranes:
            if count == M:
                break
            
            for i in range(positions[crane]):
                positions[crane] -= 1
                
                if checked[positions[crane]] == 0:
                    checked[positions[crane]] = 1
                    count += 1
                    break
                
        answer += 1

    print(answer)