[백준][이분 탐색][매개변수 탐색] 2110.공유기 설치

2110.공유기 설치

 

• 풀이

매개변수 탐색: 최적화문제를 결정 문제로 바꾸어 탐색하는 기법
     →현재 상황에서 조건을 만족할 수 있는가?'를 확인한 뒤 
          조건의 만족 여부('Yes' or 'No)에 따라서 탐색 범위를 좁혀서 해결

• 공유기 범위를 mid로 잡음
  • l=1 (최소 거리 1)
  • r=가장 끝집끼리의 거리 = house[-1]-house[0]
• cnt>=c: 
  • 거리가 딱 맞거나 짧아서 더 나옴
  • 가장 끝점에 걸리면 +1 을 했기 때문에 c보다 크게 나올때도 result=mid 해준다

n, c = map(int, input().split())
house = sorted(list(int(input()) for _ in range(n)))

# 공유기 사이 거리 (1이 최소)
l = 1
r = house[-1]-house[0]
result = 1

while l <= r:
    mid = (l+r)//2
    last = house[0]
    cnt = 1  # 처음 하나는 무조건 설치

    for i in range(1, n):
        if house[i] >= last+mid:
            cnt += 1
            last = house[i]

    if cnt >= c:
        result=max(result, mid)
        l = mid+1
    else:
        r = mid-1

print(result)