[알고리즘] 백준 공유기 설치 - 이진탐색

포스트를 작성하기 전에 밑의 블로그의 아이디어를 참고했다는 것을 미리 알립니다!

(참고 해당 블로그 링크 : https://hongcoding.tistory.com/3)

 

✏️문제 링크 :

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

2110번: 공유기 설치

코딩테스트 연습 - 메뉴 리뉴얼

---

✏️해답 sourceCode :

n, c = list(map(int,input().split()))
array=[]
for i in range(n):
    num = int(input())
    array.append(num)
array.sort()


def binary_search(start,end):
  while start<=end:
    count=1
    current = array[0]
    mid = (start + end)//2
        
    for i in range(1,n):
      if array[i] >= current + mid: # 공유기를 설치 가능
        count+=1
        current = array[i]

    if count>=c:  # 공유기 거리를 짧게 설정하여 공유기가 더 많이 설치 되었다면
      global answer
      start=mid+1 # 공유기 거리를 넓힘
      answer = mid  # 업그레이드
      
    else: # 너무 공유기 거리를 넓게 설정하여 공유기를 덜 놓았다면
      end=mid-1 #공유기 거리를 줄임
    
answer = 0
binary_search(1, array[-1]-array[0])
print(answer)

이진탐색 유형이라고 써있지 않았다면 어떤 유형의 알고리즘으로 풀어야 할지 많이 헷갈렸을 것 같다.
가장 인접한 두 공유기 사이의 거리를 최대로 하게끔 코드를 짜야 하는 것이다.

그렇게 하기 위해선 최대한 공유기를 효율적으로(더 많은 집이 와이파이를 즐김) 설치하고 그 중에서 가장 인접한 공유기 거리를 찾으면 되는 것이다.

효율적으로 설치하기 위해서는 '공유기 사이의 거리'를 하나의 값으로 정한 다음,
이 거리로 공유기를 설치했을 때 공유기를 모두 설치 할 수 있나?
할 수 있다면 더 거리를 늘렸을 때도 설치 할 수 있나?를 보기 위해서 거리를 좀 더 늘리고
할 수 없다면 공유기를 더 설치할 수 있겠금 거리를 줄여보는 것이다.

여기서 공유기 거리를 찾는 과정을 이진탐색으로 하는 것이다!!! 
(이진탐색 알고리즘을 다 안다고 가정하겠습니다)
start = 최소거리(1)
end = 최대거리 (맨 왼쪽집과 맨 오른쪽집)
이렇게 잡고 mid = (start + end) //2로 설정한다음 (mid  = 임의의 공유기 사이의 거리)
거리를 늘릴 때는 start = mid+1
거리를 줄일 때는 end = mid-1
이렇게 하면서 최대한 공유기 사이의 거리를 늘리는 것!

 

1. 양 끝의 거리의 중간값을 공유기 거리로 설정 
2. 집마다 들리면서 공유기 거리보다 길면 공유기를 심고 그렇지 않으면 공유기를 심지 않음
3. 총 심은 공유기의 갯수와 문제에서 주어진 c(공유기 수)를 비교함
    3.1 심은 공유기의 갯수가 c보다 많다는 것은 공유기 거리를 너무 짧게 설정하여 비효율적으로 공유기를 설치했다는 의미이다
          따라서 공유기의 거리를 늘리기 위해 start = mid +1
    3.2 심은 공유기의 갯수가 c보다 적다는 것은 공유기 거리를 너무 길게 설정하여 공유기를 다 심지 못했다는 의미이다.
         따라서 공유기의 거리를 줄이기 위해 end = mid-1

2,3을 반복하면 되는 것이다