[백준] 2110번 공유기 설치 (feat.Binary Search)이분 탐색

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

2110번: 공유기 설치

 

접근

문제에서 주어진 x의 좌표 범위를 봤을 때, 이분탐색으로 문제풀이를 접근해야 한다고 생각한다.

그렇다면 어떤 것을 이분탐색 해야할까?

문제의 핵심은, 공유기 사이의 좌표 간 거리중에 C개의 공유기를 설치할 수 있는 최대거리를 구하는 것이다.

즉, 공유기 사이의 거리로 가능한 최소와 최대를 정하여 해당 범위를 이분탐색 해야한다.

특정 거리를 기준으로 설치가능 여부를 판단하여, 그에따라 mid값을 기준으로 왼쪽, 오른쪽을 범위를 갱신한다.

이 과정을 start가   end보다 커질때까지 반복한다.

우선, 이분탐색을 해야하므로 주어진 배열을 정렬해야 한다.

그리고 거리의 최소는 당연히 1이 될 것이다.

거리의 최대는 정렬된 배열에서 양 끝값을 빼주면 구할 수 있다.

이렇게 구한 최소와 최대 사이에서 이분탐색을 진행하며 된다.

이분탐색 과정에서는 특정 거리 mid가 문제에서 주어진 조건을 만족하는지 확인해야 하는데,

문제에서 주어진 공유기의 개수를 모두 설치했을 때 가능한 간격이 맞는지 확인 해야한다.

공유기 설치 문제의 목적은 C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 것이다.

1. 초기값 = 중간값: 특정 간격을 기준으로 가능한 위치에 공유기를 설치한다.
2. 설치한 후에는 다음과 판단한다.
   • 공유기 수가 더 설치되어야 한다면, 간격을 줄인다.
   • 공유기 수를 줄여야한다면, 간격을 늘린다.

결국 구해야하는 최대 간격은, C개의 공유기를 설치할 수 있는 최대 길이(mid)이다.

이진탐색의 시간복잡도는 O(logN)이지만, 문제의 조건을 확인하는 과정때문에 O(N)이 걸릴 것으로 예상된다.

 

n, c = map(int, input().split())   # 집의 개수 n , 공유기의 개수 c
house_pos = []  # 집의 좌표를 저장할 리스트 생성

for i in range(n):  # n개의 집좌표 입력받아서 저장
    a = int(input())
    house_pos.append(a)

# 이분탐색을 위해 집의 좌표를 오름차순으로 정렬
house_pos.sort()

start = 1   # 최소거리
end = int(house_pos[-1]-house_pos[0])   # 최대거리

while start <= end:
    mid =(start + end)//2
    count = 1   # 현재 설치되어있는 공유기의 갯수
    set_up = house_pos[0]   # 바로 이전에 공유기가 설치된 곳

    for i in range(1, len(house_pos)):
        if house_pos[i]-set_up >= mid:  # mid(거리) 보다 바로이전에 공유기가 설치된 곳과 현재 설치하려는 곳의 거리가 긴 경우
            set_up = house_pos[i]       # 이전 공유기가 설치된 장소를 저장한 set_up에 공유기를 설치하고 위치를 갱신하여 저장함
            count = count + 1           # 공유기가 설치된 갯수 +1

    if count >= c:                      # 현재 설치되어 있는 공유기의 갯수가 C보다 많으면,
        start = mid + 1                 # 가능한 길이의 범위를 늘린다. (공유기와 공유기 사이의 거리가 더 커지므로 공유기 설치 갯수를 줄이기 위함)
    else:                               # 현재 설치되어 있는 공유기의 갯수가 C보다 적으면,
        end = mid - 1                   # 가능한 길이의 범위를 줄인다. (공유기와 공유기 사이의 거리가 더 줄어드므로 공유기 설치 갯수를 늘리기 위함)

print(end)