알고리즘 - Python / 백준 - 1092번 : 배

1092번: 배 (acmicpc.net)

1092번: 배

 

---

풀이

• 크레인의 개수와 각각 크레인이 들 수 있는 최대 무게가 주어지고 , 박스 숫자와 박스의 무게가 주어질 때 , 크레인이 모든 박스를 옮기려면 최소 몇 분이 걸리는지 출력하는 문제다.
• 무거운 박스를 들 수 있는 크레인 일 수록 무거운 박스를 드는 것이 시간을 줄이기에 유리하므로 그리디 스타일의 문제라고 생각했다.
• 크레인이 들 수 있는 최대 무게와 박스 무게를 저장한 배열을 오름차순으로 정렬하고 크레인 배열 뒤에서 부터 for문을 돌려 박스를 들 수 있는지 확인하였다.
• 박스도 오름차순으로 정렬되어있으므로 뒤에서부터 체크하여 나아간다.
• 즉 현재 존재하는 박스들 중 가장 무거운 박스를 들 수 있으면 , 들고나가라는 뜻이다.
• 이미 가져다 놓았는지 아닌지 확인하기 위한 check_box 배열을 사용하였고 , 조금이라도 시간을 줄이기 위해 현재 크레인이 들 수 있는 최대 무게가 박스들 중 최소 무게보다 작다면 for문을 돌지 않고 바로 제외시켜 버렸다.

 

import sys
n = int(sys.stdin.readline())
crain = list(map(int, sys.stdin.readline().split(" ")))
m = int(sys.stdin.readline())
box = list(map(int, sys.stdin.readline().split(" ")))
box_check = [0 for i in range(len(box))]
crain.sort()
box.sort()
ans = 0
if crain[len(crain)-1] < box[len(box)-1]:
    print(-1)
else:
    pp = len(box)
    while True:
        for i in range(len(crain)-1,-1,-1):
            if pp == 0:
                break
            if crain[i] >= box[0]:
                for o in range(len(box)-1,-1,-1):
                    if box[o] <= crain[i] and box_check[o] == 0:
                        box_check[o] = 1
                        pp -= 1
                        break
        ans += 1
        if pp == 0:
            break
    print(ans)

---