[백준] 1654번 파이썬 - 이분탐색

문제요약 (1654. 랜선 자르기)

 

1654번: 랜선 자르기

 

 

풀이를 위한 부연 설명

• 이분탐색을 이용하는 정석적인 문제이다.
• 원하는 개수의 랜선이 나왔다면
  • 해당하는 길이보다 더 작게 잘라도 원하는 개수만큼의 랜선이 나오는지 탐색하고
• 아니라면 자르려는 길이를 수정한다.

 

코드 

import sys
input = sys.stdin.readline

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

start = 1
end = max(lines)

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

    cnt = 0
    for l in lines:
        cnt += l // mid

    if cnt >= n:
        start = mid + 1
    else:
        end = mid - 1

print(end)

 

 

 

기억할 점

• 이분탐색 유형의 코드를 기억하자