공유기 설치 - 백준 2110번 (이진 탐색, 파라메트릭 서치)

03 Feb 2021 in ALGORITHM

‘풀이시간 50분 , 시간제한 2초, 메모리제한 128MB, 백준 2110 (취코테 369p)’

공유기 설치 - 백준 2110번
처음 접근할때 굉장히 난해했었다. 파라메트릭 서치 문제인지는 알겠으나 구현을 어떤식으로 해야할지 너무 막막했었다. 방법은 생각보다 간단했다. 접근은 쉬우나 해결이 너무 난해했다;;

우선 집의 위치를 받은 후에 정렬을 해준다.
이후에 집들간의 갭(거리)의 최소부터 최대를 생각해보면 최소 갭은 당연히 바로 옆에 붙어있는 경우인 1이고, 최대는 가장 먼 집과 가장 앞에 있는 집과의 갭이다.
mid를 이 최소 최대의 사잇값으로 설정한다. 그리고 첫번째 집의 위치에 공유기를 설치하고 이후에 공유기를 설치할 곳을 두번째 집부터 순차적으로 탐색한다.
첫번째 집의 위치에서 갭의 중간값인 mid가 더해진 거리가 현재 집의 위치보다 짧거나 같다면 현재 집의 위치에 공유기를 설치한다.
이렇게 설치한 횟수가 C보다 작다면 갭을 줄여야 하므로 end = mid - 1로 둔다. C와 같거나 크다면 현재 갭을 기록하고 갭을 넓힌다. 갭이 최대이면서 C를 만족해야 하기 때문이다.

N, C = map(int, input().split())

house = []

for _ in range(N):
  house.append(int(input()))

house.sort()

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

while (start <= end):
  count = 1
  mid = (start + end) // 2
  value = house[0]
  for i in range(1, N):
    if house[i] >= value + mid:
      value = house[i]
      count += 1

  if count >= C:
    start = mid + 1
    result = mid

  else:
    end = mid - 1

print(result)