[Boj] 랜선자르기 1654(python)

문제링크 : https://www.acmicpc.net/problem/1654

이진탐색 연습문제이며, 먼저 입력된 랜선들을 정렬한다.

start를 1으로 end를 max(pipes)로 설정한다(필자는 시간복잡도 고려해서 pipes[-1]을 사용).

이때 start를 0으로 할 경우, NameError를 일으키는 반례가 존재하므로 유의

이진 탐색을 하되, 조금 더 최적화하기 위해서 bisect_left(pipes, mid)를 사용함

import sys
from bisect import bisect_left


K, N = map(int, input().split())
pipes = []
for _ in range(K):
    tmp = int(sys.stdin.readline())
    pipes.append(tmp)
pipes.sort()
start = 1
end = pipes[-1]

while start <= end:
    result = 0
    if start > end:
        break
    mid = (start + end) // 2
    for pipe in pipes[bisect_left(pipes, mid):]:
        if mid != 0:
            result += pipe // mid

    if result < N:
        end = mid - 1
    else:
        answer = mid
        start = mid + 1

print(answer)