[이진탐색] 공유기설치

문제

2110번. 공유기 설치

접근

가능한 집 사이의 거리를 이진탐색을 통해 찾아나가야겠다

뼈대 코드

def cnt_possibile_n(arr, mid) : #두 공유기간 거리 주면 최대 몇대 설치가능한지 계산하는 함수
  return 0



# 가장 인접한 두 공유기간의 거리 -> 이진탐색으로 계속 좁혀나가며 찾는다
N, C = map(int, input().split())
arr = []
for _ in range(N) : arr.append(int(input()))

arr.sort()
left, right = 0, len(arr)-1
answer = 0

while left <= right : 
  mid = (left+right)//2
  possibile_n = cnt_possibile_n(arr, mid)     
  if possibile_n >= mid : # 더 넓은 간격으로 해도 된다 -> 더 큰 수 탐색
    answer = mid
    left = mid+1
  else : # 더 좁은 간격으로 놔야한다
    right = mid-1 

이렇게 뼈대를 짰다

코드

def cnt_possibile_n(arr, mid) : #두 공유기간 거리 주면 최대 몇대 설치가능한지 계산하는 함수
  value = arr[0]
  for i in range(1, len(arr)) : # 앞에서부터 차근차근 설치
    if arr[i] >= value + mid : 
      value = arr[i]
      cnt += 1
    return cnt 

# 가장 인접한 두 공유기간의 거리 -> 이진탐색으로 계속 좁혀나가며 찾는다
N, C = map(int, input().split())
arr = []
for _ in range(N) : arr.append(int(input()))

arr.sort()
left, right = arr[1] - arr[0] #집의 좌표 중 가장 작은 값
answer = arr[-1] - arr[0]

while left <= right : 
  mid = (left+right)//2 
  possibile_n = cnt_possibile_n(arr, mid)     
  if possibile_n >= mid : # 더 넓은 간격으로 해도 된다 -> 더 큰 수 탐색
    answer = mid # 최적의 결과 저장
    left = mid+1
  else : # 더 좁은 간격으로 놔야한다
    right = mid-1 

print(answer)

cnt_possibile_n 함수를 짜느라 애먹었다.

책을 참고했는데, 왜 맨 왼쪽부터 배치하는 것이 정답임을 보장하지 않는다고 생각했기 때문이다. 이렇게 그리디 하면 반례가 생긴다고 생각했다. (두번째 칸 부터 공유기를 놓는 경우만이 정답인 경우 등) 그래서 검색하다가

"정답이 되는 배치 중에 가장 왼쪽 집부터 두는 배치가 반드시 존재합니다.

하지만 모든 정답이 되는 배치가 왼쪽 집부터 둔 것은 아닙니다."

[https://www.acmicpc.net/board/view/31633](백준 질문: 이분 탐색으로 문제를 풀면 반례가 생길수 있지 않나요?)

증명도 있다.

하아아 내가 이걸 즉석에서 바로 증명할 수 있을까 ㄱ-