BaekJoon2110_공유기 설치

공유기 설치

풀이

우선 이 문제는 이분탐색을 이용하여 풀어야 한다. 하지만 이분탐색을 하기위해 start 와 end 조건을 어떻게 설정해야 하는지 때문에 애를 먹었던 문제이다.
이 문제에서는 기존 기본문제와 다르게 인덱스값을 start,end로 두는게 아닌 각 공유기간의 최소거리와 최대거리를 start, end로 두어야 한다.
1. 집의 개수와 공유기의 개수를 n,c로 입력받는다.
2. start = 1(설치된 공유기 간 최소거리), end = home[-1] - home[0](설치된 공유기 간 최대거리)를 설정한다.
3. 가장 앞의 집에 공유기를 처음에 설치 후 이분탐색 시작
4. 만약 공유기의 개수가 2개면 최대거리는 첫 집부터 마지막 집이 되므로 바로 출력
5. 이분탐색을 진행해 가면서 cnt(공유기의 개수)가 c보다 커지면 공유기 간의 거리를 더 길게 설정할 수 있으므로 설치거리(mid)를 더 늘려가며 다시 이분탐색
6. c개 보다 갯수가 더 적어지면 거리를 더 좁혀야 하므로 mid를 줄여가며 이분탐색
7. 반복이 종료되면 result(정답) 도출 가능

#정답코드
import math

n,c = map(int,input().split())

home = []

for i in range(n):
    home.append(int(input()))

home.sort()

start = 1
end = home[-1] - home[0]
result = end
        
if c < 3:
    print(result)
else:
    while start <= end:
        mid = (start+end) // 2
        point = home[0]
        cnt = 1
        
        for i in range(1,len(home)):
            if abs(home[i] - point) >= mid:
                cnt += 1
                point = home[i]
        if cnt >= c:
            result = mid
            start = mid + 1
        elif cnt < c:
            end = mid - 1
    print(result)