[BOJ 1092] 배 (Python)

복습 요망!!

풀이

처음에는 오름차순 정렬을 통해 crane으로 박스를 옮겨주었다.

(Ex) crane 무게제한 : 6 8 9
box 무게 : 2 5 2 4 7

↓ 2개 다 오름차순 정렬

crane 무게제한 : 6 8 9
box 무게 : 2 2 4 5 7

↓ 박스 고름

크레인 : 6 8 9 / 6 8 9
박스들 : 2 2 4 / 5 7

위와 같은 방식으로 풀려했다. 하지만, 이는 틀린 방법(문제에서 주어진 테스트 케이스만 통과함)이다. 왜일까? 기존의 예제에서 box 값만 수정하였다.

(Ex) crane 무게제한 : 6 8 9
box 무게 : 2 5 2 4 9 9

↓ 2개 다 오름차순 정렬

crane 무게제한 : 6 8 9
box 무게 : 2 2 4 5 9 9

↓ 박스 고름

크레인 : 6 8 9 / 6 8 9
박스들 : 2 2 4 / 5 9 9
2번 크레인이 8의 무게제한으로 인해 무게가 9인 박스를 옮길 수 없다. 따라서 해당 로직은 -1을 답으로 판단하게 된다.

하지만, 정답은
크레인 : 6 8 9 / 6 8 9
박스들 : 4 5 9 / 2 2 9
이다. 모든 박스를 옮기는데 2분이 걸리게 된다. (크레인으로 옮길 수 있는 박스의 조합은 여러 개일 수도 있음!)

---

---

문제의 포인트는 크레인이 몇 번째 box를 옮겼는지를 저장해주는 position=[]리스트 활용과 내림차순 정렬이다. 내림차순 정렬 후에 crane의 무게제한을 만족하는 가장 최적의 box를 crane으로 옮겨주게 된다. 즉, 현시점에서 crane 무게제한 - box 무게가 최소가 되도록 하는 box를 해당 crane으로 옮겨준다. 이는 내림차순 정렬을 했기에 가능하다.

그리고 시간 복잡도를 줄이기 위해 position=[]리스트를 활용한다.

position[index] = value를 보자. index번의 crane이 value-1번 box를 옮긴 것을 의미한다. (온전히 본인의 생각이다. 지적 환영합니다!)

어떻게 활용하는지 간단하게 살펴보자.

(Test Case)
3
6 8 9
6
4 5 9 2 2 9

↓ 내림차순 정렬

crane 무게제한 : 9 8 6
box 무게 : 9 9 5 4 2 2
position : 0 0 0

↓ position=[]을 활용한 박스 옮기기 시작

---

① 화물을 배에 싣는 1번째 타임

crane 무게제한 : 9 8 6
box 무게 : 9(v) 9 5 4 2 2 --> 'v' 표시는 이미 box를 crane으로 옮겼다는 의미
position : 1 0 0

position[0] = 1이 되었다. 이는 1번 크레인이 0번 박스를 옮겼다. 즉, 1번 크레인이 무게가 9인 박스를 옮긴 것이다.

↓

crane 무게제한 : 9 8 6
box 무게 : 9(v) 9 5(v) 4 2 2
position : 1 3 0

position[1] = 3이 되었다. 이는 2번 크레인이 2번 박스를 옮겼다.

↓

crane 무게제한 : 9 8 6
box 무게 : 9(v) 9 5(v) 4(v) 2 2
position : 1 3 4

position[2] = 4이 되었다. 이는 3번 크레인이 3번 박스를 옮겼다.

↓

---

② 화물을 배에 싣는 2번째 타임

crane 무게제한 : 9 8 6
box 무게 : 9(v) 9(v) 5(v) 4(v) 2 2
position : 2 3 4

position[0] = 2이 되었다. 이는 1번 크레인이 1번 박스를 옮겼다.

※ 이전에 position[0] = 1이다. 이로 인해 0번 박스부터 다시 탐색하는 것이 아닌 이전에 저장한 1번 박스부터 옮길 수 있는지 탐색한다. (화물을 배에 싣는 2번째 타임이라고 해서 position을 0으로 초기화하지 않는다. 본인은 초기화해도 된다고 생각하나 초기화할 시 시간 복잡도가 늘어나므로 초기화 안하는 것이 더 좋다고 생각한다.)

↓

crane 무게제한 : 9 8 6
box 무게 : 9(v) 9(v) 5(v) 4(v) 2(v) 2
position : 2 5 4

position[1] = 5이 되었다. 이는 2번 크레인이 4번 박스를 옮겼다.

↓

crane 무게제한 : 9 8 6
box 무게 : 9(v) 9(v) 5(v) 4(v) 2(v) 2(v)
position : 2 5 6

position[2] = 6이 되었다. 이는 3번 크레인이 5번 박스를 옮겼다.

이로 인해 모든 박스를 다 옮기게 되었고, 2분 후에 모든 박스를 옮길 수 있게 된다. 이러한 방식으로 풀면 시간 초과 없이 풀 수 있게 된다.

코드

import sys

input = sys.stdin.readline
N = int(input())
crane_limit = list(map(int, input().split()))
M = int(input())
boxes = list(map(int, input().split()))

# crane의 무게제한에 맞춰 가장 최적의 box를 옮긴다.
# 즉, (crane 무게제한 - box 무게) 가장 최소가 되도록 crane으로 box를 옮긴다.
# --> 그러기 위해서는 내림차순 정렬한다. 내림차순 정렬을 해주었기 때문에 이렇게 고를 수 있다.
crane_limit.sort(reverse=True)
boxes.sort(reverse=True)

# 내림차순 정렬 후 가장 큰 무게의 box가 가장 큰 crane 무게제한보다 크면
# 모든 박스를 배로 옮길 수 없다고 판단!
if boxes[0] > crane_limit[0]:
    print(-1)
    sys.exit(0)

# crane이 옮긴 box가 몇 번째인지 저장하는 리스트
# (Ex)
# crane[0] = 1 -> (0+1)번 crane은 직전에 0번 box를 옮김
# crane[1] = 4 -> (1+1)번 crane은 직전에 3번 box를 옮김
# crane[2] = 5 -> (2+1)번 crane은 직전에 4번 box를 옮김
position = [0] * N

# 옮긴 박스를 방문처리 해주기 위한 리스트
visited = [False] * M
count, ans = 0, 0

while True:
    # 모든 box 다 옮겼으면 종료
    if count == len(boxes):
        break
    # 모든 crane을 동시에 움직이는데
    for i in range(N):
        # crane이 "position[i]번째 box(직전에 (position[i] - 1)번째 box를 골랐으므로 position[i]번째 부터) ~ 마지막 box까지"
        # 탐색하도록 하는 while문
        while position[i] < len(boxes):
            # box를 crane으로 아직 안 옮겼고, 무게 제한보다 가벼운 box를 crane으로 옮길 수 있다면
            if not visited[position[i]] and boxes[position[i]] <= crane_limit[i]:
                visited[position[i]] = True
                position[i] += 1    # position[i]의 value는 옮긴 박스의 번호 + 1
                count += 1  # 옮긴 box 개수 + 1
                break
            # 조건 만족 못하면 다음 box를 해당 crane으로 옮길 수 있는지 탐색하기 위한 증가
            position[i] += 1
    ans += 1

print(ans)