[백준] 2110(파이썬) 공유기 설치

2110번
binary search 이분탐색 문제이다.

문제를 요약해보면

• 집은 N개가 있고, 설치할 공유기는 C개가 있다.
• 이때 집의 좌표 x1,...,xn이 주어지고, 공유기는 집에만 설치가 가능하다.
• 이때 가장 인접한 두 공유기 사이의 거리를 최대로 해야한다.

우선 문제를 처음 접했을때, 많이 헤맸다. 일반적인 이분탐색으로 생각하고 문제를 풀기 위해 start와 end를 잡아보려고 했다.

처음에는 그냥 주어진 집의 좌표의 최소를 start, 좌표의 최대를 end로 잡으면 될것 같았다. 문제는 이처럼 start, end를 통해 구한 mid 값으로 공유기 갯수를 어떻게 구할지가 의문이었다.

이에 대한 아이디어로 현재 구해야 되는 값을 주목해봤다.

가장 인접한 '두 공유기 사이의 거리'

그렇다. 두 공유기 사이의 거리가 커야한다.
즉, 집들의 위치를 for문을 이용해 하나씩 확인한다. 이때, 확인하는 집과 첫집 사이의 간격이 mid 이상이면, 공유기를 설치할 수 있기 때문에 공유기 갯수를 늘려준다. 그럼 이제 공유기 설치위치에서 mid 이상의 간격을 갖는 다음 집을 찾아주는 방식을 반복하면, mid에 따른 공유기 설치 갯수를 알 수 있다.

그럼 이것을 바탕으로 설치 공유기 갯수가 적으면, 갯수를 늘려줘야 하므로 mid 값을 줄이는 end= mid-1을 해준다.
반대로 갯수가 너무 많으면, 줄여줘야하므로, start=mid+1을 해주는것이다.

그럼 이것을 코드로 표현해보겠다.

import sys
input=sys.stdin.readline

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

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

result=0

def bs(start,end):
    while start<=end:
        mid=(start+end)//2

        cnt=1 #h[0]에 이미 설치를 했다고 가정.
        ts=h[0] #시작
        for i in range(n):
            if h[i] - ts >=mid:
                cnt+=1
                ts=h[i]
        if cnt>=c:
            result=mid
            start=mid+1
        else:
            end=mid-1
    return result

if c==2:
    print(h[n-1]-h[0])
else:
    print(bs(1,h[n-1]-h[0]))
    #최소, 최대거리 (최소거리가 1이 아닐수도있는데 1로 잡는것은 그냥 러프하게 1부터 잡는것.)

이분탐색은 start,end의 범위와 구하고자 하는 목적만 제대로 파악하면 쉽게 풀 수 있을 것 같다.