[백준 1092번] 배 (python)

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

기록

(greedy 8일차) 처음 고안한 방법은 크레인과 박스 모두 내림차순으로 정렬한 후, 가장 큰 크레인부터 반복문 돌면서 큰 박스를 평균값 혹은 다음 크레인보다 무거운 박스이 있을 때까지 박스 개수를 세어 각 크레인의 짐 개수 중 최댓값을 찾으려고 했었다. 내가 놓친 부분은 두 번째 크레인부터는 더 무거운 크레인과 박스를 나눌 수 있다는 점이었다. 따라서 이전 크레인들까지 고려하여 각 크레인이 필수로 실어야하는 박스 개수를 세어 그 중 가장 큰 값을 찾아 반환하도록 고쳤다. 다음은 내가 통과하지 못한 반례이다! 

3
4 7 10
9
2 5 5 6 6 7 8 9 9
틀린답 : 4
답 : 3

 

문제의 핵심은 각 크레인이 필수로 실어야하는 박스 개수를 세어 그 중 가장 최댓값을 찾는 것이다. 필수로 실어야하는 박스 개수는 전체 박스 개수의 평균 이상이어야하며, 다음 크레인에 싣지 못하는 짐이 있다면 그보다 더 실어야한다. 다음 크레인부터는 현재까지의 박스개수를 크레인 수로 나눈 값이다.

 

코드

import math

N = int(input())
crains = list(map(int, input().split()))
M = int(input())
boxes = list(map(int, input().split()))
crains.sort(reverse=True)
boxes.sort(reverse=True)

if boxes[0]>crains[0] : print(-1)
else :
    maxcount = mincount = math.ceil(M/N)
    idx, count = 0, 0
    for i, crain in enumerate(crains[1:], start=1):
        count = 0
        while idx<M and (crain<boxes[idx] or count<mincount) :
            idx+=1
            count+=1
        if idx/i > maxcount : maxcount=math.ceil(idx/i)
    print(maxcount)

 

먼저 박스를 싣지 못하는 경우를 조건문을 걸어 따로 실행한다.

 

위의 경우를 제외하고는,

반복문을 돌며 각 크레인이 필수로 실어야하는 박스 개수를 계산하여 그 중 최댓값을 찾는다.

각 크레인은 전체 박스개수의 평균인 최솟값보다는 박스를 많이 실어야 하기 때문에, 최솟값을 설정해놓는다.

 

첫번째 크레인은 최솟값 혹은 다음 크레인에 싣지 못하는 박스가 있을 때까지 개수를 세어 필수 박스 개수를 계산하고,

두번째 크레인부터는 이전 크레인의 박스 개수를 포함한 필수 박스 개수를 위와 같은 방법으로 계산하여 첫번째 크레인과 동등하게 나눈 값으로 계산한다.

이 과정을 반복하여 각 크레인이 실어야하는 박스 개수 중 최댓값을 반환한다.