[알고리즘/그리디] 1092번 : 배 - python

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

1092번: 배

 

---

• 문제
• 소요시간: 30분 초과(실패)

---

• 설계하기(접근방법) 

1. 입력받기

크레인 수

크레인 리스트

박스 수

박스 리스트를 입력받는다

 

2. 구현하기

이 문제의 핵심은 가벼운 박스의 경우

무게를 많이 들 수 있는 크레인과

적게 들 수 있는 크레인 모두 들 수 있으므로

이를 어떻게 분배해서

최소의 시간만에 박스를 옮기느냐 이다

 

처음에는 무게 범위대로 배분을 한 후

각 크레인보다 무거운 크레인에 배분을 하는 식으로 문제를 푸려고 했으나

시간이 상당히 많이 소요되었다

 

결국 무거운 크레인 순서대로 순회하며

박스가 무거운 순서대로

너 이 박스 감당 가능하냐?

라는 식으로 대입을 하면

모든 크레인이 1사이클을 공평하게 배분받을 수 있다

그렇게 박스가 없어질때까지 순회하면

 

최소 시간이 나온다

 

 

 

3. 출력하기

최소 시간을 출력한다

---

• 코드(출력)

import sys

input = sys.stdin.readline

crane = int(input())
crane_weight_limit = list(map(int,input().split()))
box = int(input())
box_weight = list(map(int,input().split()))

crane_weight_limit.sort(reverse= True)
box_weight.sort(reverse= True)

time = 0

if box_weight[0] > crane_weight_limit[0]:
    print(-1)
    sys.exit()

while box_weight:
    for crane in crane_weight_limit:
        for box in box_weight:
            if crane >= box:
                box_weight.remove(box)
                break
    time += 1

print(time)

---

• 얻어갈 부분

1. 세세하게 구현하다 시간을 지나치게 사용했다. 결국 가장 큰 포인트는, 어떻게 박스를 배분해서 시간이 최소로 들게 하냐이다. 모든 크레인을 순회하며 무거운 박스 순서대로 배치한다면 결국 모든 크레인에게 박스 1사이클씩 제공되는 것이다

 

2. sys.exit()을 통해 원하는 부분을 프린트하고 종료할 수 있다. 익혀보자