[Python] boj no. 1092 : 배

Problem

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

Idea

옮길 수 있는 최대 중량은 크레인마다 다를 수 있지만 옮기는 시간은 모두 1로 동일하다. 또한 크레인은 동시에 움직인다. 모든 박스를 옮기는 데 필요한 시간은 모든 크레인을 균형적으로 이용할수록 짧아지게 된다. 모든 크레인을 균형적으로 이용하기 위해서는 무게 중량이 큰 크레인이 충분히 무거운 박스를 할당받아 무게 중량이 작은 크레인이 할당받을 기회를 뺏지 않아야 한다. 따라서, 최소 시간을 구하기 위해서는 각 크레인이 가능한 무거운 박스를 옮겨야 한다.

다음과 같은 과정을 통해 각 크레인이 옮길 박스를 할당하였다.

1. 우선 박스의 무게가 무거운 순서대로 박스를 정렬하였다.
2. 이후, 무게 제한이 큰 크레인부터 박스를 탐색하여 가능한 박스를 할당한다.
3. 모든 크레인의 할당이 끝나면(할당받지 못하는 크레인이 존재할 수도 있음.) 시간을 증가시킨다.
4. 2~3의 과정을 모든 박스가 옮겨질 때까지 반복한다.

위 과정을 통해 각 시간마다 크레인들은 가능한 가장 무거운 박스를 할당받게 된다.

마지막으로, 모든 박스를 옮길 수 없는 경우 -1을 출력하는 케이스까지 구현하여 제출하였다.

Code

import sys

input = sys.stdin.readline

N = int(input())
crane = sorted(map(int, input().split()), reverse=True)
M = int(input())
box = sorted(map(int, input().split()), reverse=True)

time = 0
if box[0] > crane[0]:
    time = -1
else:
    while box:
        for c in crane:
            for b in box:
                if c >= b:
                    box.remove(b)
                    break

        time += 1
            
print(time)

Comment

python으로 제출하면 시간초과가 발생하여 pypy로 제출하여 통과하였다.

모든 박스가 하나의 크레인으로만 옮길 수 있을 경우에 시간 복잡도가 O(NM^2)이 되고, 시간 제한이 2초일 때 python이 가능한 최대 연산 횟수인 4천만번을 넘어서기 때문으로 보인다.

반복문에서 유리한 pypy를 사용했을 때 시간 내에 통과할 수 있었다.