[BOJ / PYTHON] 1654. 랜선 자르기

from sys import stdin

input = stdin.readline

N, M = map(int, input().split())

arr = list(int(input()) for _ in range(N))

arr.sort()

def binary_search(S, E):
    global M

    mid = (S + E) // 2

    cnt = 0

    if mid == S or mid == E:
        for i in arr:
            cnt += i // E

        if cnt >= M:
            print(E)
            quit()
        else:
            print(mid)
            quit()


    for i in arr:
        cnt += i // mid
        if cnt >= M:
            break

    if cnt < M:
        binary_search(S, mid)
    elif cnt > M:
        binary_search(mid, E)
    else:
        binary_search(mid, E)

if N != 1:
    binary_search(1, arr[-1])
else:
    for i in range(arr[0], 0, -1):
        if arr[0] // i >= M:
            print(i)
            quit()

풀이.

우선, 가능한 가장 큰 값을 찾기 위해서 이분탐색으로 값을 찾는다.
그러나, 항상 mid 값이 정답이 아니므로, 이에 필요한 예외처리를 진행한다.
그리고, 원하는 랜선의 갯수가 1일때의 예외처리 역시 진행한다.