[백준] 1654 랜선 자르기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1654
• 🔑 이분탐색
  • 기준 값 (mid) 값으로 각각의 줄을 나눠서 n개를 나눌 수 있는 최댓값을 찾는다.
  • mid 값으로 n개의 줄을 만들 수 없으면 오른쪽 포인터 값 r을 mid 값 -1로 바꿔준다.
  • 만들 수 있으면 왼쪽 포인터 값 l을 mid 값 +1로 바꾼다.(n개를 만들 수 있는 최댓값을 찾기 위해)

 

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
lines = [int(input()) for _ in range(k)]

l = 1
r = 2**31
mid = 0

while l <= r:
    cnt = 0
    mid = (l+r) // 2

    for line in lines:
        cnt += line // mid
    
    if n > cnt:
        r = mid - 1
    else:
        l = mid + 1

print(r)