[Python] 백준 1092번 : 배

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

1092번: 배

---

💡 문제 풀이

그리디 알고리즘 문제이다.

 

그리디 알고리즘 문제답게 가장 최선의 경우를 먼저 따지면 된다.

즉, 크레인이 남아있는 박스 중 가장 무거운 박스를 옮길 수 있는지 따지면 된다.

우선 가장 큰 무게를 드는 크레인이 가장 무거운 박스를 못 옮기면 -1을 return 한다.

-1이 아닌 경우는 모든 박스를 옮길 수 있다는 뜻이므로 while 문을 돌린다.

시간을 줄이기 위해서 지금 선택한 크레인이 남아있는 박스 중 가장 가벼운 박스를 옮기지 못한다면

continue를 통해서 넘어가 준다.

✔️ 느낀 점

처음에 제출한 코드가 시간 초과가 나길래 한참을 고민했는데 pypy로 제출하니까 정답이었다. 다른 분의 코드를 보니까 python3으로도 풀 수 있길래 continue 문을 사용하는 것으로 시간을 절약했다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
cranes = list(map(int, input().split()))
M = int(input())
boxes = list(map(int, input().split()))

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

cnt = 0

if boxes[0] > cranes[0]: cnt = -1
else:
    while boxes:
        for c in cranes:
            if boxes and c < boxes[-1]:
                continue
            for b in boxes:
                if c >= b:
                    boxes.remove(b)
                    break
        cnt+=1
        
print(cnt)