[BOJ] 2792: 보석 상자(Python)

2792번: 보석 상자

문제 설명

가장 많은 보석을 가진 학생의 보석 개수가 질투심 수치라고 한다. 한 학생은 한 색깔의 보석만을 받을 수 있을 때, 질투심 수치를 최소화해보자.

나의 풀이

import sys
input=sys.stdin.readline
    
def func():
    n,m=map(int,input().split())
    gem=[]
    for _ in range(m):
        gem.append(int(input()))
    s=1
    e=max(gem)
    while s<=e:
        m=(s+e)//2
        tmp=0
        for i in gem:
            if i%m==0:
                tmp+=i//m
            else:
                tmp+=i//m+1
        if tmp>n:
            s=m+1
        else:
            e=m-1
    return s

print(func())

한 학생이 가지는 보석의 수가 질투심을 뜻하기 때문에, 이 값을 이분 탐색으로 찾는다. 한 학생이 가지는 보석 수를 늘리면 보석을 받는 학생 수가 줄어드는 반비례 관계가 성립한다. 이 논리를 이용해서 보석을 받는 학생 수가 n이하인 조건에서 한 학생이 가지는 보석 수를 최소화하면 된다.

시간복잡도

각 보석의 최대 개수가 10^9이므로 이분 탐색에는 log10^9의 시간이 소요된다. while문 안에서 보석의 색깔만큼 계산을 수행하기 때문에 전체 시간복잡도는 O(log^9310^5)이다.