[알고리즘] 백준 2110번 문제

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

 

2110번: 공유기 설치

 

이문제는 이진탐색을 활용하여 푸는 문제이다.

 

반복적으로 gap을 설정하여 c개 이상의 공유기를 설치할 수 있는 경우를 찾는다.

 

먼저,start, end를 설정하여 최소 gap과 최대 gap 을 설정한다.

 

예제를 활용하여 코드를 구현해 보자.

 

n,c = 5,3
arr = [1,2,4,8,9]
start = arr[1] - arr[0]
end = arr[-1] - arr[0]
mid = (start + end) // 2

5개의 집이 있고 3개의 공유기가 있고 arr에 집들의 좌표라고 하면

start = 1, end = 8, mid=  4가 된다.

 

1,2,4,8,9

mid가 4라고 했을 때, 공유기를 설치할 수 있는 좌표가 1, 8 이렇게 2개이다.

그런데 3개의 공유기를 설치해야하므로, gap는 더 작아져야한다.

end = mid-1로 했을 때

mid = 2

 

1,2,4,8,9

 

공유기를 3개 설치할 수 있다. 그러면 가장 최대로 큰 거리를 구해야하므로,

gap를 증가시킨다.

mid = 3일때 더이상 gap을 증가시킬 수 없으므로, 최적의 상태가 된다.

 

이것을 코드로 구현하면 아래처럼 나타낼 수 있다.

 

n ,c = map(int, input().split(' '))

arr = []
for _ in range(n):
  arr.append(int(input()))

arr = sorted(arr)
start = arr[1] - arr[0] #최소 gap
end = arr[-1] - arr[0]  #최대 gap
result = 0

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

  if cnt >= c:
    start = mid + 1
    result = mid
  else:  #c개 이상 공유기를 설치할 수 없는 경우
    end = mid - 1
  
print(result)