[이진 탐색 알고리즘] 랜선 자르기 S3

기출 : BOJ #1654

 

변경할 값은 랜선의 길이이고 체크할 함수는 만들 수 있는 랜선의 개수를 출력한다

 

최댓값을 출력하기 때문에 범위를 줄여가면서 최댓값을 갱신한다

 

# input
answer = 0
k, n = map(int,input().split())
lan = list()
for _ in range(k):
    lan.append(int(input()))

# sort
lan.sort()

def check(val):
    global lan, n
    res = 0
    for l in lan:
        res += (l//val)
    return res

def bs(st, en, target):
    global answer
    if st>en:
        return -1
    mid = (st+en)//2
    val = check(mid)
    if val>=target:
        answer = mid
        bs(mid+1, en, target)
    else:
        bs(st, mid-1, target)

bs(0, 2**31-1, n)
print(answer)