[백준_이분탐색] 2110번 - 공유기설치

문제

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

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

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

입력

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

출력

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

 

 

풀이

 

이 코드에서 가장 인접한 공유기의 최대 거리를 찾는 핵심 아이디어는 이진 탐색을 활용하여 최적의 거리를 찾아내는 것입니다. 

 

이 과정을 구체적으로 설명하겠습니다.

1. 먼저, 집의 좌표를 오름차순으로 정렬합니다. 이렇게 정렬하면 집들이 일직선 상에 위치하게 됩니다.

2. 이진 탐색을 통해 최대 거리를 찾습니다. 이진 탐색을 사용하여 거리의 범위를 좁혀나가는데, 시작점(start)는 1로 설정하고, 끝점(end)는 첫 번째 집과 마지막 집 사이의 거리로 설정합니다.

3. 이진 탐색의 각 단계에서 중간 거리(mid)를 계산합니다. 이 중간 거리를 기준으로 공유기를 설치해보고, 그 때 설치되는 공유기의 개수를 확인합니다.

4. count_installed_routers 함수를 사용하여, 중간 거리(mid)로 설치되는 공유기의 개수를 구합니다. 이 함수는 각 집 간의 거리가 중간 거리(mid) 이상이면 공유기를 설치하는 방식으로 동작합니다.

5. 만약, 중간 거리(mid)로 설치되는 공유기의 개수가 목표 개수(C) 이상이면, 현재 중간 거리(mid)를 기록하고, 최소 거리를 늘려서 더 큰 값을 찾기 위해 시작점(start)을 mid + 1로 이동합니다.

6. 만약, 중간 거리(mid)로 설치되는 공유기의 개수가 목표 개수(C) 미만이면, 최소 거리를 줄여서 더 작은 값을 찾기 위해 끝점(end)를 mid - 1로 이동합니다.

7. 이렇게 이진 탐색을 반복하면, 최대 거리를 찾는 과정을 수행하게 됩니다. 이때, 가능한 최대 거리 중 가장 큰 값을 결과로 반환하면 가장 인접한 공유기의 최대 거리를 구할 수 있습니다.

요약하면, 이진 탐색을 활용하여 가능한 최대 거리를 조절하면서 공유기를 설치하는 과정을 반복하여, 가장 인접한 공유기의 최대 거리를 찾아내는 것이 이 코드의 핵심 아이디어입니다. 이 방법은 최적의 거리를 찾는데에 효율적이며, 이진 탐색을 사용하기 때문에 빠른 실행 시간을 가집니다.

 

 

 

소스 코드

 

# 집 좌표와 최대 거리를 이용하여 공유기를 설치한 개수를 세는 함수
def count_installed_routers(houses, max_distance):
    installed_routers = 1  # 최소한 첫 번째 집에는 공유기를 설치
    last_installed_router = houses[0]  # 마지막으로 공유기를 설치한 집의 좌표
    
    # 모든 집에 대해 반복
    for house in houses:
        # 현재 집과 마지막으로 설치한 공유기 사이의 거리가 max_distance 이상인 경우
        if house - last_installed_router >= max_distance:
            installed_routers += 1  # 공유기를 추가로 설치
            last_installed_router = house  # 마지막으로 설치한 공유기 위치를 현재 집으로 업데이트
    
    return installed_routers  # 설치된 공유기 개수 반환

# 공유기를 설치할 최대 거리를 이진 탐색을 통해 찾는 함수
def binary_search_routers(houses, C):
    start = 1  # 최소 거리
    end = houses[-1] - houses[0]  # 최대 거리 (가장 먼 집과 가장 가까운 집 사이의 거리)
    result = 0  # 결과값 초기화
    
    # 이진 탐색 실행
    while start <= end:
        mid = (start + end) // 2  # 중간 거리 설정
        # 중간 거리로 설치한 공유기 개수가 목표 개수보다 크거나 같을 경우
        if count_installed_routers(houses, mid) >= C:
            result = mid  # 결과값 업데이트
            start = mid + 1  # 최소 거리를 늘려서 더 큰 값을 찾기 위해 오른쪽으로 이동
        else:
            end = mid - 1  # 최소 거리를 줄여서 더 작은 값을 찾기 위해 왼쪽으로 이동
    
    return result  # 최대 거리 반환

# 입력 받기
N, C = map(int, input().split())  # 집의 개수와 공유기 개수 입력
houses = []  # 집 좌표를 저장할 리스트

# 집 좌표 입력 받기
for _ in range(N):
    houses.append(int(input()))

# 집 좌표 정렬
houses.sort()

# 이진 탐색을 활용하여 최대 거리 찾기
max_distance = binary_search_routers(houses, C)

# 결과 출력
print(max_distance)  # 가장 인접한 두 공유기 사이의 최대 거리 출력