[BOJ] [Python] 2110번 : 공유기 설치

이진탐색을 이용하여 풀었다.

 

 

low는 '공유기와 집' 사이의 최소 간격, high는 최대 간격으로 잡았다.

 

※ 현재 mid 값에 설치된 공유기 개수 찾기

'집 위치 - 공유기가 설치된 지점'가 mid보다 크다면 설치가 가능하다.

n개의 집에 몇 개의 공유기가 설치될 수 있는 가?

 

=> 현재 mid 값으로 설치된 공유기 개수 >= 설치해야 할 공유기 개수라면?

:  mid값이 작은 것이다. 즉, 간격이 좁은 것이다. 간격을 더 늘려도 된다.

(만약, 개수가 같아서 혹은 개수를 더 줄일 수 없다면 result값에 저장해놓은 값을 출력한다.)

 

=> 현재 mid 값에 설치된 공유기 개수 < 설치해야 할 공유기 개수라면?

: mid값이 큰 것이다. 즉, 간격이 넓은 것이다. 간격을 더 좁혀도 된다.

 

 

num = list(map(int, input().split()))

input_n = num[0] # 집 수
input_c = num[1] # 공유기 수

x_home = sorted([int(input()) for x in range(input_n)]) # 집 위치

def BSearch(n, c, x_h):
    low = 1 # 최소 간격
    high = x_h[-1] - x_h[0] # 최대 간격

    while(low <= high):
        mid = (low + high) // 2 # 공유기 간격

        count = 1
        now_h = x_h[0]

        # 집 위치 - 공유기 설치된 지점 >= mid : 설치 가능
        for i in range(1, n):
            if(x_h[i] - now_h >= mid):
                count += 1
                now_h = x_h[i]

        if(count < c): # 간격이 크다 -> 설치하려는 공유기 개수가 모자란다.
            high = mid - 1

        else: # 간격이 좁다 -> 설치하려는 공유기 개수가 많다 or 같다.
            result = mid
            low = mid + 1
    return result

print(BSearch(input_n, input_c, x_home))