백준 1092번: 배 (파이썬)

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

1092번: 배

 

문제

 

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

 

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

 

입력

 

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

 

풀이

 

처음에는 단순히 크레인과 박스를 내림차순 정렬한 뒤, 크레인의 순서대로 옮길 수 있는 박스를 리스트에서 pop하면 된다고 생각했다. 하지만 이 방법은 시간 초과 문제가 발생했고, 더 줄일 방법이 떠오르지 않아 구글링 결과 PyPy3를 사용하면 된다고 했다.

일단은 그렇게 제출했지만, 나중에 Python3로도 통과할 수 있는 방법을 찾아 보려고 한다.

 

소스 코드

 

n = int(input())
w_limit = list(map(int, input().split()))
m = int(input())
w = list(map(int, input().split()))

w_limit.sort(reverse = True)
w.sort(reverse = True)

if w[0] > w_limit[0]:
    print(-1)
else:
    cnt = 0
    while w:
        cnt += 1
        i = 0
        j = 0
        while i < n and w:
            while j < len(w):
                if w_limit[i] >= w[j]:
                    w.pop(j)
                    break
                else:
                    j += 1
            i += 1
    print(cnt)