[백준] 1654번 랜선 자르기 (python)

1. 문제

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

2. 풀이

이분탐색을 활용해 각각 중간값으로 나눠주는 것을 반복해 나가며 나눈 갯수가 n보다 많으면 분모가 더 크다는 것이기에 분자의 값을 줄여주고(초기값의 크기를 키움) 아닌경우는 마지막 값의 크기를 줄인다.

3. 코드

import sys

k,n = map(int, sys.stdin.readline().split())
arr = []
for i in range(k):
    arr.append(int(sys.stdin.readline()))

start = 1
end = max(arr)
while start <= end:
    mid = (start + end) // 2
    cnt = 0

    for i in arr:
        cnt += i // mid

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