[BinarySearch] 랜선 자르기

여기서 계속 헤멨던 이유

 

기존 사용하던 BinarySearch Iterative

n, m = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
# Using start, mid, end
start = 1
end = max(array)

# Binary Search
# H = 0
while(start <= end):
    total = 0
    mid = (start+end)//2
    for x in array:
        total += x // mid
    if total < m: 
        end = mid-1
    else: 
        start = mid+1
        H = mid # 

print(H)

문제에 맞는 BinarySearch

import sys
K, N = map(int, input().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(lan) #이분탐색 처음과 끝위치

while start <= end: #적절한 랜선의 길이를 찾는 알고리즘
    mid = (start + end) // 2 #중간 위치
    lines = 0 #랜선 수
    for i in lan:
        lines += i // mid #분할 된 랜선 수
        
    if lines >= N: #랜선의 개수가 분기점
        start = mid + 1
    else:
        end = mid - 1
    print("start: {} end: {} mid: {} lines: {} N: {} ".format(start, end, mid, lines, N))
    
print(end)

최대 랜선의 길이를 찾는 것이기 때문에 if 조건절(if lines >= N:) 여기서도 탐색을 멈추지 않고 계속 진행하면서

end값을 찾으면 되는 것이다.