[Python] 랜선 자르기 - 백준 (이진탐색)

해당 글은 백준 1654번 '랜선 자르기' 문제를 다룬다.

문제

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

1654번: 랜선 자르기

 

설명

해당 문제는 이진탐색으로 O(logN)의 시간복잡도로 해결할 수 있는 문제이다.

이전에 풀었던 나무자르기 이진탐색 문제와 비슷한데, 다른 점은 count를 mid로 나눈 몫의 갯수로 구하므로 mid가 0이 되지 않도록 start는 1부터 진행해야 한다.

 

코드

k, n = map(int, input().split())
arr = [int(input()) for _ in range(k)]

start, end = 1, max(arr)
result = 0
while start <= end:
    mid = (start+end)//2
    count = 0
    for i in range(k):
        count += (arr[i]//mid)

    if count >= n:
        result = mid
        start = mid + 1
    else:
        end = mid - 1
print(result)