https://www.acmicpc.net/problem/1092
시간 2초, 메모리 128MB
input :
- N (1 <= N <= 50)
- 크레인의 무게 제한 (1 <= 무게 <= 1000000)
- M (1 <= M <= 10000)
- 박스의 무게 제한 (1 <= 무게 <= 1000000)
output :
- 박스를 배로 옮기는데 드는 시간의 최솟값을 출력
- 옮길 수 없으면 -1을 출력
조건 :
- 모든 크레인은 동시에 움직인다.
- 처음 생각했던 방식은 모든 크레인이 동시에 움직이는데 움직이지 않는 크레인이 존재해서 틀렸다.
이를 해결하기 위해 크레인의 무게 제한보다 같거나 작은 가장 큰 박스를 각 크레인에 할당 해 주는 것이다.
우선 무게 제한보다 같거나 작은 박스들 중 가장 큰 값을 찾으려면 내림 차순 정렬을 한 후 제일 앞에서 부터 확인하다 조건에 합당한 것이 있다면 그것이 옮겨지는 박스인 것이다.
그렇다면 동시에 움직이는 것은 어떻게 해야 하나. for문을 이용해 크레인에 대해 반복하게 하면 된다.
그리고 이를 박스가 다 비어있을 때 까지 수행한다면 우리가 원하는 결과를 얻을 수 있다.
import sys
from collections import deque
n = int(sys.stdin.readline())
crain = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
weight = list(map(int, sys.stdin.readline().split()))
crain.sort(key= lambda x : -x)
weight.sort(key= lambda x : -x)
if weight[0] > crain[0]:
print(-1)
exit(0)
cnt = 0
while len(weight) > 0:
cnt += 1
for item in crain:
for i in range(len(weight)):
if item >= weight[i]:
del weight[i]
break
print(cnt)
