파이썬) 백준 알고리즘 | 2792번 : 보석 상자

https://www.acmicpc.net/problem/2792

2792번: 보석 상자

백준 2792 '보석 상자' 문제입니다.

이분 탐색 문제인데

제가 이분 탐색 응용이 좀 부족해서 dictionary를 이용했습니다.

is_possible 함수에서 True로 봔환한 것들을 dict 형태에 집어 넣고 

마지막에 정렬한 뒤 최솟값을 출력하도록 하였습니다.

원래는 이 과정을 할 필요가 없지만 제가 이분탐색에서 left, right, mid, ret 설정을 아직 잘 이해 못해서 

이런 방법으로 구현하였습니다.

import sys
import math
input = sys.stdin.readline
n, m = map(int, input().split())
jewel = []
for _ in range(m):
    a = int(input())
    jewel.append(a)

def is_possible(num):
    cnt = 0
    for i in range(m):
        cnt += math.ceil(jewel[i]/num)
    if cnt <= n:
        return True
    else:
        return False

left = 1
right = 10**9+1
ret = 0
s = {}
while left <= right:
    mid = round((left + right)/2)
    if is_possible(mid):
        right = mid - 1
        s[mid] = 1
    else:
        left = mid + 1
        ret = max(ret, mid)

a = list(s.keys())
a.sort()
print(a[0])