백준 2792 보석상자

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

2792번: 보석 상자

 📌 해결과정

우선 문제를 읽고 문제를 풀기위해 필요한 조건들을 정리했다.

학생들의 질투심을 최소화 한다 = 한 학생이 갖는 같은 색상의 보석의 갯수를 최소화 한다 

 

1. 모든 보석을 남김없이 학생들에게 나누어 줘야한다.

2. 한 학생은 같은 색상의 보석만 가질 수 있다.

3. 보석을 갖지 못하는 학생이 있을 수 있다.

 

어떻게 풀어야 할지 감을 잡지 못하다가 두번 째 예시를 통해서 힌트를 얻고 풀었다.

 

이렇게, 예제 2를 통해서 몫과 나머지를 이용해야 하는 방법을 찾았다.

만약 검은색 보석이 7개가 있고 질투심이 3이라면 3 3 1 로 나누어서 학생에게 줘야하고,

각 학생은 같은 색상의 보석만 가질 수 있으므로 3명의 학생에게 나누어 줘야 한다.

남기는 보석이 없어야 하므로 무조건 3명을 써야한다.

 

🧐 이분 탐색

 

질투심 A 로 나누어준 학생의 수가 실제 학생 수 보다 많다 = 질투심이 작다.

따라서 A 질투심 보다 작은 경우에 대해서 탐색 할 필요가 없다.

 

질투심 A 로 나누어준 학생의 수가 실제 학생 수 보다 적다 = 질투심이 크다

따라서 A 질투심 보다 큰 경우에 대해서 탐색 할 필요가 없다.

 

질투심의 최솟값을 찾아야 하므로 질투심이 큰 값부터 줄여 나가야 했다.

 

start = 1 이다. 만약 0 이면 mid 값이 0 이 되는 경우가 생긴다 따라서 값이 무한으로 발산 하므로 런타임 에러가 발생한다.

end 는 보석 색상 중에서 가장 갯수가 많은 보석이다.

 

📌 코드

import sys

input = sys.stdin.readline

students, jewel_type = map(int, input().split())
colors = [int(input()) for _ in range(jewel_type)]
colors.sort()


start = 1
end = colors[-1]
ans = 0

while start <= end:

    tmp_students = 0
    mid = (start + end) // 2

    for color in colors:
        if color % mid == 0:
            tmp_students += color // mid
        else:
            tmp_students += color // mid + 1

    if tmp_students <= students:
        end = mid - 1
        ans = mid
    else:
        start = mid + 1

print(ans)