[백준 1654] 랜선 자르기 - 파이썬 :: 이진탐색, 파라메트릭탐색

대표적인 이진탐색, 파라메트릭 탐색 문제였다.

mid 값을 답 후보로 두고 start 와 end 를 조정해나가며 푸는 문제였다.

 

import sys
k, n = map(int, input().split())
array = [int(sys.stdin.readline().strip()) for _ in range(k)]

start = 1
end = max(array)

while start <= end:
    total = 0
    mid = (start + end) // 2

    # total 값 구하기
    for x in array:
        total += x // mid

    # total 비교해서 start, end 조정
    if total < n: # total이 적은거면, 너무 크게 자른거니까, end 줄여야함
        end = mid - 1
    else:
        answer = mid
        start = mid + 1

print(answer)

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

1654번: 랜선 자르기

이진탐색으로 구현했는데 처음에 시간초과가 나서 혹시 input() 때문일까 싶어서 sys.stdin.readline()으로 바꿔보기도 했는데 시간초과가 나더라.

어이없게도 total 값 구하는 부분에서 // 로 안풀고 처음에 while문으로 반복 돌려서 푸는 바람에.. 하핫

그 부분을 수정하니 런타임 에러 (ZeroDivisionError) 가 나더라.

start를 0으로 잡아놔서 그런 듯 해서 start 초기값을 1로 주었더니 통과했다.