[BOJ] 2110 / 공유기 설치 / Python 파이썬

[BOJ] 2110 / 공유기 설치 / Python 파이썬

[BOJ] 2110 / 공유기 설치 / Python 파이썬

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

2110번: 공유기 설치

 

풀이

풀이 방법을 떠올리기가 힘들었던 이진탐색 문제였다.

 

"공유기 사이의 거리를 최대로 하는 설치 간격" 을 찾는 문제인데 이 조건을

 

• "집 사이의 간격이 X 이상이 가능한 집의 수 == 공유기 대수"

로 다시 생각하여야 풀 수 있었다.

 

1. 집 사이의 간격을 이진탐색으로 찾기
2. 간격을 주어진 집의 좌표에 대입하여 가능한 경우의 수 계산
3. 가능한 경우의 수 == 공유기 대수 <- 정답

 

N, C = map(int, input().split())

house = []

for _ in range(N):
    house.append(int(input()))

house.sort()
end = house[-1] - house[0]
start = 1
res = 0
while start <= end:
    mid = (start+end)//2

    cnt = 1

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

    if cnt < C:
        end = mid - 1
    else:
        start = mid + 1
        res = mid

print(res)