[백준] 2110번번 (python 파이썬)

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

 

문제를 이해를 못했다..

출력에

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다. 라고 써있는데

인접한 두 공유기 사이 최대 거리가 뭔소린지 몰라서 문제부터 이해했다...

 

이해한 내용)

공유기 개수 3

좌표 : 1 2 4 8 9

 

만약

거리 = 2 라면

1에 설치하면 1+2 = 3   -> 다음 설치할 공유기 위치는 3이상인 좌표이다.

2에는 설치 못한다.

4에 설치 4+2 = 6 -> 다음 설치할 공유기 위치는 6이상인 좌표이다.

8에 설치 8+2 = 10 -> 다음에 설치할 공유기 위치는 10이상인 좌표이다.

9에는 설치 못한다.

끝----- 설치한 공유기 개수 3개

거리가 2일때 만족

 

만약

거리 = 3 라면

1에 설치하면 1+3 = 4   -> 다음 설치할 공유기 위치는 4이상인 좌표이다.

2에는 설치 못한다.

4에 설치 4+3 = 7 -> 다음 설치할 공유기 위치는 7이상인 좌표이다.

8에 설치 8+3 = 11 -> 다음에 설치할 공유기 위치는 11이상인 좌표이다.

9에는 설치 못한다.

끝----- 설치한 공유기 개수 3개

거리가 3일때 만족

 

이런식이다 즉 만족하는 거리중 최대값을 찾는것이다.

 

n, c = map(int, input().split(' '))
xs = [int(input()) for _ in range(n)]
xs.sort()

def binary():
    left = 1
    right = max(xs) - 1

    while left <= right:
        mid = (left + right) // 2

        count = 1
        wifi = min(xs) + mid

        for i in range(1, len(xs)):
            if wifi <= xs[i]:
                count += 1
                wifi = xs[i] + mid

        if count >= c:
            left = mid + 1
        elif count < c:
            right = mid -1
    return right

print(binary())