배 - [백준 1092번]

배 - 백준 1092번

문제

• 항구에서 배에 화물을 실어야함
• 모든 화물은 박스에 들어있음
• 항구에는 크레인 N대, 1분에 크레인당 한개씩만 실을 수 있음
• 모든 크레인은 동시에 움직임

입력

• 첫째 줄 - N : 크레인 수
• 둘째 줄 - 각 크레인의 무게 제한 ( 1,000,000 보다 작거나 같음)
• 셋째 줄 - M : 박스의 수
• 넷째 줄 - 각 박스의 무게 ( 1,000,000 보다 작거나 같음)

출력

• 모든 박스를 배로 옮기는데 드는 시간의 최솟값 출력

코드

import sys

def solution(craneWeightLimits, boxWeights):
  result = 0

  craneWeightLimits.sort(reverse=True) # 내림차순
  boxWeights.sort(reverse=True) # 내림차순

  if craneWeightLimits[0] < boxWeights[0] : # 모든 박스를 배로 옮길 수 없을 때 -1 반환
    return -1

  # 모든 크레인이 동시에 움직일 경우 최솟값
  normal = len(boxWeights) // len(craneWeightLimits)
  normal = normal if len(boxWeights) % len(craneWeightLimits) == 0 else normal + 1
  result = normal

  i, j, count = 0, 0, 0 # craneWeightLimits 인덱스, boxWeights 인덱스, 카운터
  while len(boxWeights) > j: # 전체 박스 반복문
    if count >= result: # 해당 크레인이 할당량을 채울 경우 다음 크레인으로 이동
      count = 0
      i += 1
    if boxWeights[j] > craneWeightLimits[i]: # 박스 무게가 크레인이 들지 못하는 경우. 할당량을 채운 크레인들이 박스를 옮겨줌
      j += i # 할당량 채운 크레인 모두가 박스를 옮김
      result += 1 # 1분 추가
      continue
    count += 1 # 할당량 1 증가

    j += 1 # 다음 박스로 이동

  return result

N = int(sys.stdin.readline())
craneWeightLimits = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
boxWeights = list(map(int, sys.stdin.readline().split()))
print(solution(craneWeightLimits, boxWeights))