📌 [BOJ] 백준 2792 보석 상자

📖 문제

📖 예제

📖 풀이

import sys

N, M = map(int, input().split())
box = []
for _ in range(M):
  box.append(int(sys.stdin.readline()))

start = 1
end = max(box)

while start <= end:
  mid = (start + end) // 2
  cnt = 0
  for i in box:
    if (i % mid == 0):
      cnt += (i // mid)
    else:
      cnt += (i // mid) + 1
  if cnt > N:
    start = mid +1
  else:
    end = mid - 1
    result = mid

print(result)

아이들에게 나눠주는 보석의 수에 대해서 이분 탐색을 수행한다.
아이들에게 꼭 같은 수의 보석을 나눠줘야하는 것은 아니기 때문에 특정 색의 보석의 수를 나눠주는 최대 수 mid로 나눴을 때 나머지가 생기면 그것을 한 명의 아이에게 나눠준다고 생각하여 cnt를 늘려준다.
해당 cnt를 아이들의 수 N과 비교하여 cnt가 더 클 경우 나눠주는 보석의 최대 갯수를 늘려도 되기에 start 값을 mid + 1로 설정해주고, cnt가 N보다 작을 경우 end를 mid - 1로 설정해주어 위 과정을 반복한다.