백준 2110번 공유기 설치

이분 탐색은 정렬된 숫자중에서 특정값을 찾는것인데 이문제에 어떻게 접목시켜야하는지 고민했다

가장 인접한 두 공유기 사이 거리를 크게 설치한다 -> 공유기 사이거리를 최대한 떨어져서 설치해야한다

위 문제를 통해 해결해야될 것은 2가지로 생각된다

1. 집마다 거리가 각각 다르다
2. 공유기를 어떤 방법으로 설치할것인가

 

 

해결방법

1. 처음 위치를 1로 초기화하고 그에 맞는 집의 위치를 설정한다 최대는 마지막집 - 처음집 + 1이 된다

2. 이분 탐색을 이용하여 간격을 조절한다 -> (처음 집 위치 + 마지막집 위치)//2 를 통해서 mid값을 구하고 만약 mid값을 기준으로 공유기를 설치 했을때 조건에 충족 되는지 확인하고 조건에 충족되면 출력한다

조건은 mid 간격이상으로 설치했을때 입력받은 공유기 개수보다 더 크게 설치되면 start = mid +1 간격을 늘이고 더 작게 설치되면 공유기 설치 간격을 줄인다 end = mid -1이걸 반복해서 조건에 만족하는 값을 출력한다

import sys

N,C = map(int,sys.stdin.readline().split())
distance = []
distance_list = []

for i in range(0,N):
    distance.append(int(sys.stdin.readline()))

distance.sort() 

start = 1
end = distance[-1] - distance[0]  #최대거리

while start <= end:
    c = 1 #처음 집에 공유기 설치가 되므로 1로 시작한다
    k = 0 #마지막으로 공유기가 설치된 위치
    mid = (start + end)//2

    for i in range(1,N): #거리를 이분 탐색한다
        if distance[i] >= distance[k] + mid:
            c += 1 #공유기 설치개수
            k = i
   
    if c  >= C:
        start = mid + 1
        distance_list.append(mid)
    else:
        end = mid - 1

print(max(distance_list))