[DevLog][Baekjoon] 2110: 공유기 설치

01) 문제

도현이의 집 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
// output is 3

02) 풀이

• 구하고자 하는 것은 공유기 사이의 거리 D이다.
• 공유기 사이의 거리의 lower/upper bound를 정한다.
  • lower는 1 (집은 모두 다른 좌표이므로)
  • upper는 마지막 집의 좌표 - 첫번째 집의 좌표
• D의 조건을 생각해 본다.
  • 간격으로 C개의 공유기를 모두 설치 가능해야 한다.
• 조건을 만족하는 D의 최댓값을 찾는다.

# 간격을 만족하는 집의 개수를 반환합니다.
def installable(간격):
  curr = H[0] # 집 배열 H의 첫번째 집 기준으로
  for i in H[1] to end:
    if H[i] - curr >= 간격:
      cnt += 1
      curr = H[i]
  return cnt

# 조건을 만족하는 최댓값을 탐색합니다.
s, e = lower, upper
while s <= e:
  mid = (s+e)//2
  # mid를 간격으로 했을 때 설치 가능한 공유기의 수 cnt
  cnt = installable(mid) 
  if cnt < C: # 만약 모든 공유기를 설치할 수 없으면
    e = mid-1 # 더 좁은 간격을 검색
  else:
    s = mid + 1 # 간격을 넓힘 (최대를 구하기 위해)

여기에 중간중간 간격의 최댓값을 저장해주는 코드를 추가하면 된다. 공유기의 설치 가능을 체크하는 installable 부분에서 mid보다 큰 간격의 최소치를 저장해두는데, 이는 간격의 lower bound를 갱신하여 답을 구하기 위함이다.

03) 코드(파이썬)

import sys

N, C = map(int, input().split())
X = [int(sys.stdin.readline()) for _ in range(N)]
X.sort()

upper = X[-1]-X[0]  
lower = 1  
s, e = lower, upper

while s <= e:
    mid = (s+e) // 2
    cnt = 1  
    diff = upper

    curr = X[0]
    for i in range(1, N):
        if X[i]-curr >= mid:
            diff = min(diff, (X[i]-curr))  
            cnt += 1
            curr = X[i]

    if cnt < C:
        e = mid-1 
    else:
        s = mid+1  
        lower = max(lower, diff)

print(lower)