백준 1092 - 배 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/1092
풀이
크레인을 이용해서 박스를 옮기는 문제이다.
각 크레인은 특정한 무게까지의 박스를 들 수 있으며, 최소 시간 내에 모든 바스를 옮기는 것이 목표이다.
먼저 A, B 를 입력 받고, 각 박스를 각각 내림차순으로 정렬하여, 가장 무거운 박스를 가장 무거운 크레인부터 배치할 수 있도록 변경한다.
if A[0] < B[0] :
print(-1)
exit()
그리고 만약 가장 강한 크레인이 가장 무거운 박스를 들 수 없다면, 모든 박스를 옮기는 것이 불가능 하므로, -1을 출력한다.
count = 0
while len(B) > 0 :
for a in A :
if len(B) > 0 and a < B[-1] :
break
for b in B :
if b <= a :
B.remove(b)
break
count += 1
각 크레인은 들 수 있는 가장 무거운 박스를 찾고 제거한다.
그리고 모든 크레인이 한 번씩 돌고 나면 1분이 경과한 것으로 간주하다.
박스가 없어질때까지 반복하고, 모든 박스를 옮기는 데 걸린 최소 시간을 출력하면 된다.
시간 복잡도 분석
- 정렬 → O(N log N) + O(M log M)
- 반복문 → 최악의 경우 O(N * M)
즉, O(N log N) + O(M log M) + O(NM)
코드
# 백준 1092 - 배
# 분류 : 그리디
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
if A[0] < B[0] :
print(-1)
exit()
count = 0
while len(B) > 0 :
for a in A :
if len(B) > 0 and a < B[-1] :
break
for b in B :
if b <= a :
B.remove(b)
break
count += 1
print(count)
'Programming > 백준' 카테고리의 다른 글
백준 21758 - 꿀 따기 (파이썬) (1) | 2025.03.14 |
---|---|
백준 1302 - 베스트셀러 (파이썬) (0) | 2025.03.13 |
백준 2075 - N번째 큰 수 (파이썬) (0) | 2025.03.11 |
백준 16439 - 치킨치킨치킨 (0) | 2025.03.11 |
백준 17255 - N으로 만들기 (파이썬) (0) | 2025.03.10 |
댓글
이 글 공유하기
다른 글
-
백준 21758 - 꿀 따기 (파이썬)
백준 21758 - 꿀 따기 (파이썬)
2025.03.14 -
백준 1302 - 베스트셀러 (파이썬)
백준 1302 - 베스트셀러 (파이썬)
2025.03.13 -
백준 2075 - N번째 큰 수 (파이썬)
백준 2075 - N번째 큰 수 (파이썬)
2025.03.11 -
백준 16439 - 치킨치킨치킨
백준 16439 - 치킨치킨치킨
2025.03.11