백준 이진탐색 알고리즘 연습

랜선 자르기

#랜선 갯수, 원하는 갯수 입력받기
n, w = map(int, input().split())
# 랜선들 넣을 리스트 만들기
array = [int(input()) for _ in range(n)]
# 시작, 끝, 결과 넣을 자리 만들기
start = 1
end = max(array)

result = 0
# while 문으로 mid값 찾기
while start <= end:
    mid = (start+end) //2
# 자른갯수 넣을 자리 만들기
    total = 0

    for x in array:
        total += x // mid
#total갯수가 원하는거랑 같거나 크면 후보에 넣기
    if total >= w:
        result = mid
        start = mid+1
    else:
        end = mid -1
print(result)

나무자르기

#나무갯수, 원하는 길이 합
n, w = map(int, input().split())
# 나무들 넣기
array = list(map(int,input().split()))
# 시작과 끝
start = 1
end = max(array)
result = 0
#이진 탐색 반복
while start <= end:
    mid = (start+end) //2
    total = 0
    
# 잘랐을때 나무 길이 계산
    for x in array:
        if x > mid:
            total += (x - mid)
            
# 길이가 충분하면 오른쪽으로
    if total >= w:
        result = mid
        start = mid+1
              
# 길이가 부족하면 더 많이 자르기(왼쪽으로 이동)
    else:
        end = mid -1  
#최대한 크게 자른것이결과
print(result)

공유기 설치

n, w = map(int, input().split())
array = [int(input()) for _ in range(n)]
array.sort()

start = 1
end = array[-1] - array[0]
result = 0

while start <= end:
    mid = (start+end) //2
    count =1
    last = array[0]
    
    for i in range(1, n):
        if array[i] - last >= mid:
            count += 1
            last = array[i]
            
    if count >= w:
        result = mid
        start = mid +1
    else:
        end = mid-1
        
print(result)