[Python] 1092번 배

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

1092번: 배

---

 

23/09/03

 

 

그리디적으로 접근하면 풀리는 문제로, 구현이 살짝 까다로웠다.

---

 

문제 접근 방식:

 

 

생각한 방법은 다음과 같았다.

 

 

1. 크레인과 박스가 있으면 두 리스트를 모두 내림차순 정렬한다.

 

2. 만약 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인의 무게제한을 비교했을 때, 가장 무거운 박스가 더 무겁다면 어떻게 하더라도 그 박스는 옮길 수 없으므로, $-1$을 출력한다.

 

3. 그렇지 않으면 다음과 같은 방법을 따라갔다.

 

- 무거운 박스에서 가벼운 박스 순으로 살펴보며, 박스를 크레인에 실을 수 있는지 따져본다.

- 만약 크레인에 박스를 실을 수 있으면 크레인에 그 박스를 실고, 다음 크레인을 살펴본다.

(우리는 크레인을 내림차순 정렬했기 때문에, 다음 크레인은 이전 크레인보다 무게제한이 작다.)

- 만약 크레인에 박스를 실을 수 없다면, 그 박스는 이번 차례에는 실을 수 없다고 판단. 다음 박스를 실을 수 있는지 살펴본다.

(우리는 박스도 내림차순 정렬했기 때문에, 다음 박스는 이전 박스보다 무게가 적다.)

 

4. 이렇게 모든 박스를 다 살펴본 후에 동시에 크레인으로 한 번 나른다. 이후 횟수에 $+1$을 해준다.

 

5. 3~4번 과정을 모든 박스를 다 나를 때까지 반복한다.

 

 

박스를 날랐는지의 여부는 배열을 통해 체크해주는 방식으로 구현했다.

 

박스를 살펴보는 것과 크레인을 살펴보는 것은 투포인터를 통해 구현했다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 1092번 배
# 정렬, 그리디, 두포인터
import sys
input = sys.stdin.readline

N = int(input())
cranes = sorted(map(int, input().rstrip().split()), reverse = True)
M = int(input())
boxes = sorted(map(int, input().rstrip().split()), reverse = True)
if boxes[0] > cranes[0]:
    print(-1)
else:
    # 못쓰는 크레인 제거하고 시작하자
    while True:
        if cranes[-1] < boxes[-1]:
            cranes.pop()
        else:
            break
    cnt = 0
    visited = [0 for _ in range(M)]
    while sum(visited) != M:
        crane_idx = 0
        box_idx = 0
        while crane_idx < len(cranes) and box_idx < M:
            if visited[box_idx] == 1:
                box_idx += 1
            else:
                if cranes[crane_idx] >= boxes[box_idx]:
                    crane_idx += 1
                    visited[box_idx] = 1
                    box_idx += 1
                else:
                    box_idx += 1
        cnt += 1
    print(cnt)