백준 / 배 / 1092번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 배 / 1092번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/1092

 

문제 설명

---

나의 풀이

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)

그리디 알고리즘(탐욕법)을 이용하는 문제다.

1. 크레인과 박스를 내림차순으로 바꿔서 크래인이 처음에 박스를 많이 가져가도록 한다.

2. 그리고 박스의 첫번째가 크래인의 첫번재 보다 크면 바로 continue를 이용하여 다시 되돌아간다.

아마 이 과정이 없으면 시간 초과가 발생하는 것을 알 수 있다.

---

※ 알아야 할 것

 

https://newkimjiwon.tistory.com/53

탐욕(그리디) 알고리즘(Greedy algorithm)