<그리디> 1092번 배 with 파이썬

문제

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

 

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

입력

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

출력

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

정답비율

24.565%

알고리즘 분류

 #그리디 #정렬

 

import sys
input = sys.stdin.readline

n = int(input())
c_lst = list(map(int, input().split())) # 크레인 무게 제한 리스트
c_lst.sort(reverse=True)
answer = [0] * n
answer_sum = 0
m = int(input())
b_lst = list(map(int, input().split())) # 박스 무게 리스트
b_lst.sort(reverse=True)
box = 0
if b_lst[0] > c_lst[0]:
    print(-1)
    quit()

while answer_sum < m :
    j = 0
    for i in range(n):
        while j < m:
            if c_lst[i] >= b_lst[j] and b_lst[j] > 0:
                b_lst[j] = -1
                answer[i] += 1
                answer_sum += 1
                break
            j += 1
print(max(answer))

 

 - 위 방식은 오답처리를 받은 풀이이다.

 

 - 내림차순으로 정렬한 후 크레인을 돌며 들 수 있는 박스를 고르도록한다. 고른 박스는 -1로 처리하였다.

 

 - 계속 시간초과가 나길래 시간을 줄일 수 있는 방법을 총동원하였다. 첫 while문에는 배열을 sum시키는 대신 변수에 더해가도록 하여 이를 비교하였고, 두 번째 while문도 처음에는 박스의 처음부터 확인하도록 하였으나 그럴 필요없이 앞선 크레인이 확인한 박스 이후를 살피도록하였다. 따라서 while문 내부의 for과while둘을 합쳐서 m번의 확인만이 일어날 것이다.

 

 - 하지만 계속 시간초과가 났고 결국 다른사람들의 풀이를 보려고 구글링 했으나 전부 위와 같았다. 혹시나 다른가 싶어서 복사해서 제출했더니 시간초과란다. 다들 pypy로 푼 듯하다.

 

 - 그래서 백준에서 파이썬으로 성공판정을 받은 사람의 풀이를 참고하여 개선하여 풀었다. 이는 다음과 같다.

 

import sys
input = sys.stdin.readline

n = int(input())
c_lst = list(map(int, input().split())) # 크레인 무게 제한 리스트
c_lst.sort(reverse=True)
answer = [0] * n
m = int(input())
b_lst = list(map(int, input().split())) # 박스 무게 리스트
b_lst.sort(reverse=True)
if b_lst[0] > c_lst[0]:
    print(-1)
    quit()
time = (m-1) // n + 1
box = 0
while box < m:
    for i in range(n):
        if answer[i] < time and c_lst[i] >= b_lst[box]:
            answer[i] += 1
            box += 1
            break
        if c_lst[i] < b_lst[box]:
            time += 1
            break

print(max(answer))

 

 - 먼저 최선의 시간 time을 구한다. 예를들어 크레인이 3개이고 박스가 6개이면 2분이 최선이다.

 

 - 이렇게 시간을 구해두고 while문으로 박스를 순회한다. answer에는 각 크레인이 작업하는 시간을 담도록하였다.

 

 - 만약 time보다 적고 박스를 옮길 수 있다면 시간을 1분늘리고 그 다음 박스를 확인할 수 있도록 한 후 for문을 탈출한다.

 

 - 다음 박스도 가장 큰 크레인에서 확인하고 최선의 시간이 될때까지 큰크레인 순으로 담기게된다.

 

 - 만일 최선의 시간으로 각각 다 담았는데 작은 트레인에서 박스를 못 옮긴다면 시간을 1분 늘린 후 다시 큰크레인부터 확인하도록 하였다.

 

 - 이렇게하면 정답처리가 되며, 위에서 약 m*m이던 시간복잡도를 m*n으로 줄일 수 있을 것 같다.

 

 

 

---

 

 

 

참고

 

 

1092번: 배