2792번 보석 상자 S2

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

오늘도 킹받는 이분탐색 문제.

문제
사람 수와 보석의 종류, 각 보석이 몇 개가 있는지가 주어진다.
사람들에게 보석을 남기지 않고 나누어주는데 각 사람은 한 종류의 보석만 갖는다.
보석을 모두 나눠주었을 때 보석을 가장 많이 가진 사람의 보석 수가 최소가 되게 해야한다.
보석을 받지 못하는 사람도 있을 수 있다. 보석의 종류는 사람의 수 보다 적거나 같다.
가장 보석을 많이 받은 사람의 보석 수가 질투심이 된다. 이 질투심을 최소가 되게 해야한다.

문제를 보고 이분탐색일거라는 생각은 들었지만 어떻게 코드를 작성해야할지는 한참 생각을 했다. start, end, mid 값이 의미하는 것을 정의내리기가 어려웠다.

한참 고민 끝에 아래와 같이 정리를 하며 방향을 잡았다.

• 보석이 주어진 그대로 사람들에게 나누어준다. -> 보석 종류 중 가장 높은 수가 질투심이다.
• 보석을 1개씩 모두에게 나누어주어야 하는 경우도 있을 수 있다. -> 질투심은 1
  (사실 여기서 처음에 1이 아니고 0을 집어넣어서 무지하게 틀렸다. 무슨 생각으로 그랬는지..?)
• 1과 제일 많은 보석 수의 중간 값(mid)에서 시작 -> mid 값의 의미 : 인당 최대 보석 수
• mid 값대로 사람들에게 나누어주었을 때 보석이 남았다 -> 너무 잘게 나누었다 -> mid 값을 키우기 위해 start를 mid+1로 옮긴다
• 보석이 남지 않았다 -> 모두에게 잘 나누어주었거나 못 받은 사람이 있을 수도 있다. 하지만 상관은 없다. -> mid 값을 줄여서도 나누어보기 위해 end를 mid-1로 옮긴다.
• 보석이 남지 않았으니 mid값이 질투심이 될 수 있다. 기존에 저장된 질투심보다 낮다면 질투심을 mid값으로 갱신해준다. (최초의 질투심은 보석들 중 가장 개수가 많은 보석의 수)

구현하면서 실수가 엄청 많았다.
start나 end 값을 바꾸어줄 때 +1, -1을 빼먹고 그냥 start = mid, end = mid 따위로 쓰면서 무한루프를 돌게도 했고 start, end 값이 바뀌는 조건문을 이상하게 적어 틀리기도 했다. 위에 적었던대로 0으로 나누는 경우도 넣어버려 틀리기도 했다. 왜 이분탐색 문제를 풀 때는 항상 이렇게 실수가 많은지 알 수가 없다. 정말 king받는다.

from math import ceil
from sys import stdin

n, m = map(int, stdin.readline().split())
c = [0 for i in range(m)]

for i in range(m):
    c[i] = int(stdin.readline())

jealousy = max(c)
# 보석을 못 받는 학생도 있을 수 있다
# 한 사람은 항상 같은 색의 보석만 갖는다
# 보석을 가장 많이 갖는 학생의 보석이 최소가 되게 한다

# 뭘로 나누어야하지..?
# 보석 종류는 사람수보다 적거나 같다
# 주어진 그대로 배분 -> 제일 많은 보석 수가 답
# 1과 제일 많은 보석 수의 중간값에서 시작 -> 인당 최대 보석 수
# 보석이 남는다 -> 너무 잘게 나눴다 -> start를 mid + 1로 옮김
# 아니다 -> 적당히 나누었다 -> end를 mid - 1로 옮김

start = 1
end = jealousy

while start <= end:
    if (start + end) % 2 == 0:
        mid = (start + end) // 2
    else:
        mid = (start + end) // 2 + 1
    
    count = 0
    for i in range(m):
        count += ceil(c[i]/mid)
    if count <= n:
        if mid < jealousy:
            jealousy = mid
        end = mid - 1
    else:
        start = mid + 1
    
print(jealousy)