백준 2792번 파이썬 문제풀이(보석상자) - 이분탐색

---

이분탐색 문제는 대부분 출력에서 나오는 값을 이분탐색하며 찾는 방식이 많다.

이문제 또한 그러한 방식이다. 이분탐색할 질투심 x를 1~10^9 까지 범위로 잡아주고 반씩 줄여나가면서 해당 질투심일 때 필요한 사람수를 비교하여 구해진 사람수가 필요한 사람수 보다 많으면 사람수를 줄이기 위해 질투심을 높여야 하기 때문에 탐색 시작인덱스를 증가시켜주고 만약 적으면 질투심을 낮추어야 하기때문에 끝인덱스를 줄여주는 식으로 탐색하면 된다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
array = []
for _ in range(M):
    array.append(int(input()))

s = 1  # 1명부터
e = 10 ** 9  # 10^9 까지의 사람수가 존재한다.


def check(x):
    total_person = 0  # 사람수 저장

    # 현재의 질투심이 x일때의 총 사람수 계산
    for i in array:
        total_person += i // x + (i % x != 0)

    return total_person <= N  # 만약 그사람수가 N보다 적다면 True


ans = 0
while s <= e:

    mid = (s + e) // 2

    if check(mid):  # 질투심이 mid 일때 사람수가 N보다 작거나 같다면
        ans = mid  # 그 값을 질투심으로 저장 후
        e = mid - 1  # 다시 왼쪽으로 탐색
    else:  # 질투심이 mid 일때 사람수가 N보다 크다면
        s = mid + 1  # 질투심을 증가시켜서 사람수를 줄인다

print(ans)