[BOJ] 공유기 설치 - 2110 (G4)

시간 제한	메모리 제한
2 초	128 MB

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

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

풀이

이 문제는 매개 변수 탐색(Parametric Search) 문제이다. “최소 거리의 최댓값”을 구하는 문제로, 이분 탐색을 활용한다.

접근 방법

핵심 아이디어

• 결정 문제로 변환: “최소 거리가 x일 때 C개의 공유기를 설치할 수 있는가?”
• 이분 탐색으로 최적의 x를 찾는다.

풀이 과정

1. 집의 좌표를 정렬
2. 최소 거리의 범위: [1, 최댓값 - 최솟값]
3. 중간값 mid를 최소 거리로 설정
4. mid 간격으로 공유기를 설치했을 때 C개 이상 설치 가능한지 확인
   • 가능하면: mid를 증가시켜 더 큰 값 탐색
   • 불가능하면: mid를 감소시켜 더 작은 값 탐색

코드

N, C = map(int, input().split())
houses = sorted([int(input()) for _ in range(N)])

# 집 사이 최소 거리
start = 1
# 집 사이 최대 거리
end = houses[-1] - houses[0]
result = 0

# C개의 공유기를 모두 설치할 수 있는 mid를 찾기기
while start <= end:
    mid = (start + end) // 2
    count = 1
    cur_house = houses[0]

    for i in range(1, N):
        # 현재 집과의 거리가 mid보다 크거나 같을 때 -> 설치 가능
        if houses[i] - cur_house >= mid:
            count += 1
            cur_house = houses[i]

    # 가능한 경우 더 큰 mid를 탐색
    if count >= C:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

코드 설명

정렬

houses = sorted([int(input()) for _ in range(N)])

• 좌표를 정렬하여 순차적으로 탐색 가능하게 함

이분 탐색 범위 설정

start = 1
end = houses[-1] - houses[0]

• 최소 거리: 1
• 최대 거리: 가장 먼 집과 가장 가까운 집의 거리

결정 함수

count = 1
cur_house = houses[0]

for i in range(1, N):
    if houses[i] - cur_house >= mid:
        count += 1
        cur_house = houses[i]

• 첫 집에 무조건 설치
• 다음 집이 현재 집과의 거리가 mid 이상이면 설치
• 설치 가능한 공유기 개수 카운트

이분 탐색

if count >= C:
    result = mid
    start = mid + 1
else:
    end = mid - 1

• C개 이상 설치 가능: mid를 증가시켜 더 큰 거리 탐색
• C개 미만: mid를 감소시켜 더 작은 거리 탐색

시간 복잡도

• 정렬: O(N log N)
• 이분 탐색: O(log(최대거리))
• 각 이분 탐색마다 O(N) 검사
• 전체 시간 복잡도: O(N log N + N log(최대거리))

N ≤ 200,000, 최대거리 ≤ 1,000,000,000이므로:

• O(200,000 × log(1,000,000,000)) ≈ O(200,000 × 30) = O(6,000,000)
• 충분히 통과 가능

매개 변수 탐색 패턴

1. 최적화 문제를 결정 문제로 변환
   • “최댓값을 구하라” → “값이 x일 때 가능한가?”
2. 이분 탐색으로 최적값 찾기
   • 가능한 값의 범위를 이분 탐색
3. 결정 함수 작성
   • 주어진 값으로 조건을 만족하는지 판단

유사 문제

• BOJ 1654: 랜선 자르기
• BOJ 2805: 나무 자르기
• BOJ 1300: K번째 수