백준 | 2110

n개의 집 좌표(1차원)가 주어진다.

n개의 집에 공유기 c개를 설치할 때, 인접한 공유기의 최대 거리를 찾는 문제이다.

인접 공유기의 최소 거리는 1부터 시작할 테고,
최대 거리는 양 끝 좌표의 거리부터 줄어들 것이다.

그래서 이 두 값 사이의 값 중,
문제의 조건을 만족하는 최대의 값을 찾아야 한다.

그래서 아래의 흐름대로 이진 탐색으로 접근했다.

1. 적절한 공유기 사이의 거리(mid)를 찾는다.
2. 문제의 조건을 만족하는지 확인한다.
3. 조건을 만족하는 범위에서 min_len, max_len 값을 조정한다.
4. 위의 과정을 반복한다.

주의할 부분은 조건문에서의 등호 사용인 것 같다. (while low <= high, if cnt >= n 등)

코드(정답)는 다음과 같다.

# 2110

import sys

# 입력
n, c = map(int, sys.stdin.readline().split())
locations = [int(sys.stdin.readline()) for _ in range(n)]

# ans: 구하고자 하는 값(랜선 최대 길이)
ans = 0

# 이진 탐색을 위한 정렬
locations.sort()

# 이진 탐색
min_len, max_len = 1, locations[-1] - locations[0]
while min_len <= max_len:
    # mid: 설치해 보려는 공유기 간 간격
    mid = (min_len + max_len) // 2

    # 초기 설정
    latest_install = locations[0]
    cnt = 1

    # 순차적으로 인접한 공유기 사이의 거리를 확인
    for i in range(1, n):
        if locations[i] - latest_install >= mid:
            cnt += 1
            latest_install = locations[i]

            # c개 이상 설치되었다면 추가 탐색할 필요 없음
            # 이미 설치된 공유기가 조건을 다 만족하기 때문
            if cnt >= c:
                break

    if cnt >= c:
        ans = mid
        min_len = mid + 1
    else:
        max_len = mid - 1
        
print(ans)