[백준] 1654번 랜선 자르기 - 파이썬

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

1654번: 랜선 자르기

풀이

이분탐색 문제

# 백준 1654
# K개의 다른길이를 가진 전선들을 N개의 일정한 길이의 전선들로 만들어야한다.
# 이분탐색을 위한 target, start, mid를 잡아준다. 이분탐색을 최댓값을 찾을때까지 진행된다.
import sys
input = sys.stdin.readline
K, N =  map(int, input().split())          # K개와 N개를 정수로 받아준다.
lis_k = []                                 # K개의 전선들을 받아줄 리스트 작성.
for i in range(K):
    lis_k.append(int(input()))             # 전선 K개의 길이들을 lis_k에 넣어준다.
start = 1
end = max(lis_k)

while start <= end:
    cnt = 0
    mid = (start+end) // 2 # mid는 정수여야한다.
    for i in lis_k:
        cnt += i // mid
    if cnt >= N:
        start = mid + 1 # N이 크거나 같다면 크기를 더 늘려도된다.
    else:
        end = mid - 1 # N이 작다면 크기를 늘려서 더 잘게 잘라서 N을 늘려준다.

print(end)            # 왜 end인가? end는 N을 만족하는 수들의 최대값이기때문이다. start는 N+1을 만족시키는 값의 최솟값이다.

출력결과