[Problem Solving] 백준 1092번 배 문제풀이

백준 1092번 그리디 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시기 바랍니다.

 

백준 1092번 배 문제 해설

1092번: 배

물건을 옮기는데 최적의 방법은 가장 무거운 것을 들 수 있는 크레인이 가장 무거운 박스를 옮기는 것이다. 방법은 다음과 같다.

 

1. 각 크레인과 박스를 무게에 맞게 내림차순 정렬시켜준다.
2. 크레인이 들 수 있는 가장 무거운 박스를 옮긴다.
3. 모든 크레인에 대해서 해결했다면 시간을 1 올려준다.
4. 2의 과정을 반복한다.

상자를 옮기는 최소의 시간은 위의 과정으로 해결이 가능하다. 그렇다면 모든 박스를 옮길 수 없는 경우에 대하여 처리도 해줘야 한다. 옮길 수 없는 경우는 가장 무거운 것을 들 수 있는 크레인보다 무거운 박스가 존재하는 경우이다. 따라서 정렬된 크레인과 박스의 값의 첫 번째 값을 비교해서 박스의 무게가 더 크다면 옮길 수 있는 크레인이 존재하지 않다는 것을 뜻한다.

 

위의 과정을 코드로 정리하면 다음과 같다.

 

n = int(input())
data = list(map(int,input().split()))
 
m = int(input())
weight = list(map(int, input().split()))
 
timeCount = 0
data = sorted(data, reverse=True)
weight = sorted(weight, reverse=True)
 
if data[0] < weight[0]:
  print(-1)
else:
  while len(weight) > 0:
    for l in data:
      for j in range(len(weight)):
        if l >= weight[j]:
          weight.remove(weight[j])
          break
    timeCount += 1
  print(timeCount)

 

그래도 조금 생각해보면 최적의 방법을 찾을 수 있는 그리드 문제였습니다.