[백준 - Python] 1092. 배 (그리디)

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

1092번: 배

 

코드

import sys
input = sys.stdin.readline

n = int(input())
crane = list(map(int, input().split()))
m = int(input())
box = list(map(int, input().split()))

crane.sort(reverse=True)
box.sort(reverse=True)

cnt = 0
if box[0] > crane[0]: # 가장 큰 중량을 들 수 있는 크레인이 가장 큰 박스를 들지 못할 경우
    print(-1)
    exit(0)

while box:
    for c in crane:
        for b in box:
            if c >= b: # 현재 크레인이 박스를 들 수 있으면
                box.remove(b)
                break  # box 반복문 탈출 -> 다음 crane으로 이동
    cnt += 1
print(cnt)

 

처음에 문제를 읽고,

크레인 리스트와 박스 리스트 둘 다 정렬을 해야겠다는 생각을 했다.

 

근데 그리디 문제임을 알고 있었고, 가장 최선의 경우부터 따지는 것이 맞으니

내림차순 정렬을 하여, 크레인이 남아있는 박스 중

가장 무거운 박스를 옮길 수 있는지 확인하는 방법으로 접근을 하는게 맞았다.

 

내림차순 정렬을 하여

가장 큰 무게를 드는 크레인이 가장 무거운 박스를 못 옮긴다면

불가능한 경우로 판단해 -1을 출력한다.

 

그 이외의 경우에 대해서는 while문을 돌면서 크레인이 박스를 들 수 있으면

박스 리스트에서 해당 박스를 삭제하고

박스 리스트가 빈 리스트가 될 때까지 반복하면서 카운팅을 하면 된다.

 

백준에 제출할 때, python3이 아니라 pypy로 통과가 되었다.

 

python3으로도 통과가 되는 코드에 대해서 더 알아보면 좋을 거 같고,

오름차순으로 풀다 만 내 첫 코드도 수정해서 연습해보면

코드 구현 측면에서 도움이 될 것 같다.