공유기 설치

알고리즘 구분 : 이진 탐색

문제 설명 : 집 N개가 수직선 위에 존재하며, 공유기 C개를 설치해야 한다. 가장 인접한 두 공유기 사이의 거리를 최대로 할 수 있도록 공유기를 설치하여야 한다.

문제 조건 : 2 <= N <= 200,000 / 2 <= C <= N / 좌표 0 <= x <= 1,000,000,000

문제 풀이 :
1) "주어진 좌표를 토대로 이진탐색할 수 있을까?"
1-1) 가정 : "가장 좌측(또는 우측)에 무조건 공유기가 설치되어 있어야 할 것이다."
이유는 공유기가 가장자리에 존재하지 않는다면, 당연하게 인접 공유기 간의 거리가 최대로 벌어질 수 없을 것으로 판단하였다. 이 방식으로 양쪽에 공유기를 놓은 후 가운데의 공유기를 순회하면서 계산하는 방식으로 코드를 짜보려고 했으나, 공유기가 4대 이상일 경우의 설치 방식에 대하여 명확한 알고리즘을 짜지 못하였다.
--> 잘못된 접근

2) "거리를 기준으로 이진 탐색할 수 있을까?"
문제 예제와 같이, 최소 좌표와 최대 좌표의 차를 2로 나눈 몫을 기준으로 하여 최소거리에 대한 계산을 진행해보고자 했다.
2-1) 4를 최소거리로 하여 공유기를 설치할 수 있는가?
2-1-1) 설치할 수 있다. 결과 리스트에 해당 값 추가 후, 5 ~ 8 에서 더 큰 최소 거리가 존재하는지 탐색
2-1-2) 설치할 수 없다. 1 ~ 3 에서 최소 거리 존재하는지 탐색

소스 코드 :

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

data = []
for i in range(n):
    data.append(int(input()))

data.sort()

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

while start <= end:
    first = data[0]
    mid = (start + end) // 2
    cnt = 1
    
    for i in range(1, n):
        if first + mid <= data[i]:
            first = data[i]
            cnt += 1

    if cnt >= c:
        start = mid + 1
        result.append(mid)
    else:
        end = mid - 1

print(max(result))

• 문제 출처 : https://www.acmicpc.net/problem/2110
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.