BOJ 1092 배

LONGNEW·2021년 5월 11일
0

BOJ

목록 보기
229/333

https://www.acmicpc.net/problem/1092
시간 2초, 메모리 128MB
input :

  • N (1 <= N <= 50)
  • 크레인의 무게 제한 (1 <= 무게 <= 1000000)
  • M (1 <= M <= 10000)
  • 박스의 무게 제한 (1 <= 무게 <= 1000000)

output :

  • 박스를 배로 옮기는데 드는 시간의 최솟값을 출력
  • 옮길 수 없으면 -1을 출력

조건 :

  • 모든 크레인은 동시에 움직인다.

  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)

0개의 댓글