백준 2110 공유기 설치(이분탐색)

from sys import stdin
input = stdin.readline
n, c = [int(v) for v in input().split()]
x_list = [0] * n

for i in range(n):
    x_list[i] = int(input())
x_list.sort()

s, e = 1, x_list[-1]

while s<= e:
    mid = (s+e)// 2
    cnt = 1
    tmp = x_list[0]

    for x in x_list[1:]:
        if x >= tmp +mid:
            cnt += 1
            tmp = x

    if cnt >= c:
        s = mid + 1
    else:
        e = mid - 1
print(e)

주어진 n, c가 너무 크기 때문에 완전 탐색으로는 해결이 불가능 하다.
이 문제도 이분탐색으로 해결이 가능하다.

우선 각 좌표에 대한 거리를 차례대로 구해야 하기 때문에 정렬을 진행한다.
s, e를 각각 1과 좌표에서의 가장 큰 값으로 정한 후 이분탐색을 진행한다.

여기서 이분탐색으로서 mid 값은 주어지는 x 좌표에 대한 차이 즉 거리이다.

이 문제에서 생각할 점은 for 문을 통해 x 좌표를 돌면서 현재 x 좌표가 저장되어 있는 x 좌표(tmp)와 mid 값의 합보다 크거나 같은 경우가 공유기를 설치할 수 있는 경우이다. 이때 count를 세고 x 좌표를 저장해서 다음 x와 비교할 수 있게 하는 것이다.