Algorithm-배

---

백준 1092 : 문제링크

• 문제유형 :

  • 탐욕 알고리즘

• 설명

  • 크레인과 박스를 무게 기준으로 내림차순 정렬한다
  • 무거운 박스부터 크레인이 옮기도록한다
  • 크레인의 수 N, 박스의 수 M일때 시간복잡도는 O(NM)이다

• 풀이

  import sys
  
  n = int(input())
  cranes = list(map(int, input().split()))
  
  m = int(input())
  boxes = list(map(int, input().split()))
  
  if max(cranes) < max(boxes):
      print(-1)
      sys.exit()
  
  positions = [0] * n
  checked = [False] * m
  
  cranes.sort(reverse=True)
  boxes.sort(reverse=True)
  
  result = 0
  count = 0
  
  while True:
      if count == len(boxes):
          break
      for i in range(n):
          while position[i] < len(boxes):
              if not checked[position[i]] and cranes[i] >= boxes[position[i]]:
                  checked[position[i]] = True
                  position[i] += 1
                  count += 1
                  break
              position[i] += 1
      result += 1
  
  print(result)