백준 랜선 자르기 풀이, 파이썬

문제 출처

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

풀이 과정

1. 이 문제는 이분탐색으로 풀 수 있다.
2. N개보다 많이 잘라내는 값을 찾아야 하는데 더 이상 N개보다 더 많이 자를 수 있게 되면 start를 +1 시킨다.
3. 1씩 늘어나므로 end와 같아지게 되면 그것이 최대 길이가 된다.
4. 시간복잡도는 KlogN인데 N보다 많이 만들어도 되는 경우가 있기 때문에 근소한 차이가 있다.

import sys

K, N = map(int, sys.stdin.readline().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]

start = 1
end = max(lan)

while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for l in lan:
        cnt += l // mid
    if cnt >= N:
        start = mid + 1
    else:
        end = mid - 1

print(end)