[백준][이분탐색] 2792. 보석 상자

2792. 보석 상자

 

• 내 풀이 - fail
  • n이 m보다 클 경우 각 반복마다 하나의 값을 꺼내고, 그 값을 반으로 나눈 두 값을 다시 힙에 넣는다.
  • 힙의 크기가 기하급수적으로 커져서 메모리터짐

import heapq

n, m = map(int, input().split())
jewely = []
for i in range(m):
    heapq.heappush(jewely, -int(input()))

answer = 0
if n <= m:
    print(-heapq.heappop(jewely))
else:
    for i in range(n):
        if not jewely:
            break
        maxV = -heapq.heappop(jewely)
        if maxV == 1:
            continue
        half1 = maxV // 2
        half2 = maxV - half1
        heapq.heappush(jewely, -half1)
        heapq.heappush(jewely, -half2)
    print(-heapq.heappop(jewely))

 

 

• 다른 사람 풀이
  • 이 문제의 핵심은 "가장 많은 보석을 가진 학생의 보석 수(x)를 최소화"하는 것
  • → 이분 탐색을 통해 가능한 x의 범위를 좁혀 나갑

이분 탐색을 적용할 수 있는 이유

: 특정 x에 대해 보석을 분배할 수 있는지 여부를 확인하는 함수가 단조 증가하기 때문

단조 증가 함수: 함수의 입력값이 커질수록 함수의 출력값이 작아지지 않고 같거나 커지는 함수
예를 들어, f(x)가 단조 증가하면 x1 < x2일 때, f(x1) <= f(x2)가 성립

 

 

• 가장많은 보석 수가 x일 때 나눌 수 최소 인원
  • → 최대한 많은 사람이 x개씩 가져가야 최소 인원

import math
n, m = map(int, input().split())
jewely = []
for _ in range(m):
    jewely.append(int(input()))

l, r = 1, max(jewely)
result = r
while l <= r:
    mid = (l+r)//2
    tmp = 0

    for j in jewely:
        tmp += math.ceil(j/mid)  # 최대한 많은 인원이 mid 값을 가지도록
    if tmp > n:
        l = mid+1
        continue

    result = min(result, mid)
    r = mid-1

print(result)