[백준] 1092번 배

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

 

문제

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

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

 

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

 

 

풀이

크레인과 박스를 정렬하여 크레인이 들 수 있는 박스의 갯수를 각각 체크한 뒤 내가 들 수 있는 가장 무거운 영역의 박스부터 확인하고 없는 경우 한단계 가벼운 박스를 드는 형식으로 체크했다.

예제 입력에 대하여 위와 같은 형식으로 구성하였고 9의 경우에는 들 수 있는 박스가 없기 때문에
8의 박스를 드는 방식이다.

cranes.sort()
boxes.sort()
idx, count = 0, 0

입력으로 받은 크레인과 box를 정렬한다.

 

for i in range(M):
        if boxes[i] <= cranes[idx]:
            box_count[idx] += 1
        else:
            idx += 1
            box_count[idx] += 1

현재 크레인이 들 수 있는 무게보다 박스의 무게가 작은 경우에 box_count를 1 증가시켰다.
더 큰 경우에는 index를 증가시킨 뒤 box_count를 1 증가시켰다.

 

while sum(box_count) > 0:
        count += 1
        for i in range(N-1, -1, -1):
            for j in range(i, -1, -1):
                if box_count[j] > 0:
                    box_count[j] -= 1
                    break

box_count의 합이 0보다 큰 동안, 박스가 남아있는 동안 count를 증가시키면서
큰 크레인부터 역순으로 체크하였다. 나와 동일한 index의 box_count가 0이면
한단계 작은 box_count를 확인한다.

 

if cranes[-1] < boxes[-1]:
    print(-1)

박스를 옮길 수 없는 경우에는 -1을 출력해야하기 때문에 가장 무거운 박스보다 크레인이 들 수 있는 최대 무게가 작은 경우에 -1을 출력하도록 하였다.

 

문제 없이 구현한 것 같은데 답이 계속 틀리게 나왔다.
동일한 무게를 들 수 있는 크레인이 존재하는 경우에 인덱스는 더 무거운 박스를 들 수 있는 크레인이 나올 때까지 증가하여야하는데 1칸만 증가시켜서 문제가 되는 것이였다.

크레인이 1 1 2고 박스가 1 1 2 2 2라면 box_count는 [2, 0, 3]이 나와야한다.

    for i in range(M):
        if boxes[i] <= cranes[idx]:
            box_count[idx] += 1
        else:
            while boxes[i] > cranes[idx]:
                idx += 1
            box_count[idx] += 1

index를 증가시키는 부분을 다음 무게를 들 수 있는 크레인이 나올때까지 증가시켜주니 문제가 해결되었다.

 

전체 코드

import sys

N = int(sys.stdin.readline().strip())
box_count = [0 for _ in range(N)]
cranes = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline().strip())
boxes = list(map(int, sys.stdin.readline().split()))
cranes.sort()
boxes.sort()
idx, count = 0, 0

if cranes[-1] < boxes[-1]:
    print(-1)
else:
    for i in range(M):
        if boxes[i] <= cranes[idx]:
            box_count[idx] += 1
        else:
            while boxes[i] > cranes[idx]:
                idx += 1
            box_count[idx] += 1

    while sum(box_count) > 0:
        count += 1
        for i in range(N-1, -1, -1):
            for j in range(i, -1, -1):
                if box_count[j] > 0:
                    box_count[j] -= 1
                    break

    print(count)

예외가 어디서 발생하는지 몰라서 찾는 것에 시간이 많이 소모되었다.