[백준][이진탐색] 2110 - 공유기 설치

문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

구현

• '공유기 간의 거리'를 줄이면 설치 가능한 '공유기 대수'가 늘어나고
  거리를 늘리면 설치 가능한 '공유기 대수'가 줄어든다.
• 반대로, 설치 가능한 '공유기 대수'가 적다면 거리가 너무 길다는 뜻이니 
  거리를 줄여 설치 가능 대수를 늘릴 수 있고
  설치 가능 대수가 '크거나 같다면' 거리를 늘리면서 (최대거리를 구해야 하니)
  최대 거리도 만족하며 설치 가능 대수도 x와 일치하는 값을 찾을 수 있다. (-> 목표)

 

코드

import sys
input = sys.stdin.readline

def solution(arr, N, C):
  start = 1
  end = arr[-1] - arr[0]
  result = 0

  while start <= end:
    mid = (start + end) // 2  # 가장 인접한 두 공유기 사이의 거리 (gap)
    prev = arr[0]
    count = 1
    for i in range(1, N):  # 앞에서부터 차근차근 설치
      if arr[i] >= prev + mid:
        prev = arr[i]
        count += 1
    if count >= C:  # C 개 이상의 공유기를 설치할 수 있는 경우, 거리 증가
      result = mid  # Upper Bound 형식 참고
      start = mid + 1
    else:  # C 개 이상의 공유기를 설치할 수 없는 경우, 거리 감소
      end = mid - 1

  return result

N, C = map(int, input().split())
arr = [int(input()) for _ in range(N)]
arr.sort()
print(solution(arr, N, C))

요근래 공부하던 것 중 제일 이해하기 힘들었던 문제.

사실 아직까지 가장 인접한 두 공유기 사이의 거리를 뜻하는 gap이 왜 mid가 되는지 이해하지 못했다.

그 부분 빼고는 다행히 이해할 수 있었는데 

이제 이진 탐색에 대해 막 이해하고 응용하기 시작했으니 언젠가 깨닫게 될 때가 오지 않을까 싶다.

 

이진 탐색 문제들은 DFS/BFS 문제와 마찬가지로 어떤 알고리즘을 써야겠다 까지는 유추하기 쉽지만

문제에 대해 어떻게 활용할지가 제일 문제가 될 것 같다.

실제로 그리디와 이진 탐색을 같이 활용해야 되는 매우 고난이도의 문제도 대회에서 출제가 된다고 하니..

다행인 것은 코테에서 이진 탐색의 출제 빈도가 그렇게 높지 않다는 것?

 

그래도 간만에 뇌를 좀 혹사시킬만한 문제가 나와서 그런지 즐겁게 공부했던 것 같다.