백준 1092 배 🛳

문제링크

문제 이해

이 문제는 항구에서 N개의 크레인으로 M개의 화물을 옮겨야하는 문제이다.
이 때 각 화물은 박스 안에 넣어져 있으므로 '화물==박스'로 동일시하겠다.

문제의 조건은 다음과 같다.
1. M개의 박스와 N개의 크레인이 있다.
2. 입력으로 각 박스의 무게와 각 크레인의 무게 제한이 주어진다.
3. 크레인은 한번에 무게 제한을 초과하지 않는 박스 하나만 운반할수 있다.
4. 모든 크레인은 동시에 움직이고, 한번 물건을 옮기는데 1분이 걸린다.

출력해야하는 값은 모든 박스를 배로 옮기는데 드는 시간의 최솟값이고, 모든 박스를 배로 옮길 수 없으면 -1을 출력한다

코드

def canContinue(canMove):
    for cm in canMove:
        if cm == True:
            return True
    return False


def getCanCarryBoxIndex(craneWeight, boxs):
    if craneWeight < boxs[len(boxs) - 1]:
        return -1
    for i, boxWeigth in enumerate(boxs):
        if craneWeight >= boxWeigth:
            return i

# 입력 ----------------------------------------

N = int(input()) # 크레인의 개수
cranes = list(map(int, input().split())) # 각 크레인의 무게제한
M = int(input()) # 박스의 개수
boxs = list(map(int, input().split())) # 각 박스의 무게

# --------------------------------------------

cranes.sort(reverse=True)
boxs.sort(reverse=True)

canMove = [True] * N

mins = 0
while True:
    mins += 1
    # part 1
    for i in range(N):
        if len(boxs) == 0:
            break
        if canMove[i] == True:
            idx = getCanCarryBoxIndex(cranes[i], boxs)
            if idx == -1:
                canMove[i] = False
            else:
                del boxs[idx]
    # part 2
    if len(boxs) == 0: # 더 이상 옮길 박스가 없는 경우
        break
    if canContinue(canMove) == False: # 모든 박스가 크레인의 제한 무게를 초과하여 박스를 옮길 수 없는 경우
        mins = -1
        break

print(mins)

풀이

주요 아이디어는 박스가 옮겨지면 옮겨진 박스는 리스트에서 제거하는 것이다.
박스를 리스트에서 아예 제거하면 다음번 옮길 박스를 탐색할 때 리스트의 길이가 짧아지므로 탐색 시간이 점점 줄어들 것이라고 판단했기 때문이다.

파이썬에서는 del list[i]와 같이 del 명령어를 통해 i번째에 해당하는 아이템을 리스트에서 제거할 수 있다.

(1) 입력 이후 첫번째로 수행하는 것은 cranes와 boxs를 내림차순으로 정렬하는 것이다. 이는 무게가 큰 박스부터 이동시키기 위함이다.

(2) 다음으로 크기가 N인 canMove 배열을 모두 True로 초기화 시킨다.
그리고 더 이상 화물을 옮길 수 없는 크레인인 경우, 해당 크레인의canMove 값을 False로 지정해 준다. 더 이상 화물을 옮길 수 없는 크레인의 판단 조건은 남은 박스들이 모두 자신의 무게제한을 초과한 경우이다.

(3) mins는 총 소요되는 시간이고, 반복문의 한 사이클마다 1씩 증가한다.

(4) 한 사이클은 두 부분으로 나눠 설명할 수 있다.

• 먼저, part 2는 while문의 escape 조건이다.
  if len(boxs) == 0: 더 이상 옮길 박스가 없는 경우 모든 박스를 다 옮겼으므로 break를 통해 반복문을 탈출하고 소요 시간을 출력한다.
  if canContinue(canMove) == False: 옮길 박스가 남아 있지만 남아있는 모든 박스가 크레인의 제한 무게를 초과하여 박스를 옮길 수 있는 크레인이 없을 때, 반복문을 탈출하고 -1을 출력한다.

• part 1: 각 크레인에 대해 반복문을 돌리는데, 크레인을 움직일 수 있다면 getCanCarryBoxIndex 함수를 통해 옮길 박스의 인덱스를 알아낸다. 옮길 수 있는 박스가 없으면 해당 크레인의 canMove 값을 False로 바꾸고, 옮길 수 있는 박스가 있으면 해당 인덱스의 박스를 리스트에서 제거한다.