(Python/파이썬) - 백준(BOJ) 1092번 : 배

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

1092번: 배

---

• 문제 : 

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

 

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

그리디 알고리즘을 사용하여 해결할 수 있는 문제였습니다.

 

 

풀이입니다.

 

1. 모든 박스를 싣지 못하는 경우를 배제하기 위해 크레인의 무게 한도중 max값과 box의 무게 중 max값을 비교하여 가장 무거운 박스를 싣지 못한다면 -1을 출력한다.

 

2. 남아있는 박스가 있는 동안 남은 박스의 무게를 순회하여 크레인이 실을 수 있는 가장 무거운 박스를 싣게 한다.

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
crain = sorted(list(map(int,input().split())), reverse=True)
box_n = int(input())
weight = deque(sorted(list(map(int,input().split())),reverse=True))
answer = 0
if weight[0] > crain[0]:
    print(-1)
    exit()
while weight:
    curr_crain = 0
    answer += 1
    for _ in range(box_n): # M
        w = weight.popleft()
        if curr_crain < N:  # 크레인을 다 사용하지 않은 경우
            if crain[curr_crain] >= w: # 크레인에 실을 수 있는 무게인 경우
                box_n -= 1
                curr_crain += 1
            else: # 크레인에 못 싣는 경우
                weight.append(w)
        else:
            weight.append(w)
    if answer >= 10000:
        break
print(answer)