문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [int(input()) for _ in range(m)]

arr.sort()
left = 1
right = arr[-1]
res = 0
while left <= right:
    mid = (left + right) //2
    sum = 0

    for jewel in arr:
        cnt = jewel // mid if jewel % mid == 0 else jewel // mid + 1
        sum += cnt

    if sum > n:
        left = mid +1
    else:
        res = mid
        right = mid -1

print(res)

설명

이분탐색을 하는 기준을 질투심으로 정했다. 최소는 1이고 최대는 보석 중 가장 많은 개수로 정했다. ( 한 명에게 모든 보석을 다 줄 수 있기 때문이다) 그 후 보석마다 mid 값만큼 학생들에게 나눠주면서 수를 구하고 나눠준 학생들의 수가 주어진 n보다 작거나 같은 경우(학생 중 보석을 받지 못하는 학생이 존재하기 때문) res에 mid 값을 저장한 후 출력해주었다.