백준 1654번 "랜선 자르기"

문제

백준 1654번 랜선자르기

풀이

이분탐색 문제
이분 탐색을 진행하며 잘라진 선의 개수가 n값이 될 때 right값이 각 줄의 최대 길이가 된다.

Python 코드

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
line = [int(input()) for _ in range(k)]
left, right = 1, max(line)

while left <= right:
    mid = (left + right) // 2
    tmp = 0
    
    for i in line:
        tmp += i // mid
        
    if tmp >= n:
        left = mid + 1
    else:
        right = mid - 1

print(right)