[BOJ][🟡5][백준#02110] 공유기 설치

문제 출처

BAEKJOON Online Judge #2110

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제

입력

5 3
1
2
8
4
9

출력

3

My Sol

import sys
input = sys.stdin.readline

def binary_search():
    global houses, ans, N, C
    s, e = 1, houses[-1] - houses[0]
    while s <= e:
        m = (s + e) // 2
        cur = houses[0]
        cnt = 1
        for i in range(1, N):
            if houses[i] >= cur + m:
                cnt += 1
                cur = houses[i]

        if cnt < C:
            e = m-1
            continue

        s = m+1
        ans = m

N, C = map(int, input().split())
houses = sorted([int(input()) for _ in range(N)])
ans = 0
binary_search()
print(ans)

고민해도 답이 안 나와서 블로그(링크)를 참고해 풀었다.

이분탐색을 활용하는 문제였다. 이분탐색의 결과인 mid는 공유기 사이의 거리로 두고, 이 거리를 조정하며, 해당 거리 내에 집들이 분포하는지 확인하는 방식을 사용하는 것이다.

1. 첫 집부터 공유기를 설치한다.
2. 앞집(cur)과 현재 설정된 공유기 최대 거리를 더한 값과 위치가 같거나 크다면 해당 위치의 집에 공유기를 설치하고 해당 집을 앞집으로 설정한다.
3. 공유기를 설치할 때마다 cnt를 1씩 올려준다.
4. 모든 집을 조회했다면, cnt를 확인한다.
5. cnt가 공유기 개수(C)보다 작으면 공유기간의 거리가 큰 것이므로 e를 m-1로 줄인다.
6. cnt가 C보다 같거나 크면 공유기 거리를 더 키워볼 수 있으므로 s를 m+1로 지정하고, ans를 m으로 설정한다.

결과

맞았습니다!!