29_공유기 설치

2110번: 공유기 설치

 

이 문제는 N개의 집 중에, C개의 공유기를 설치하는 문제다.

단, C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 해야 한다.

 

시간 제한이 2초이고, 집의 좌표는 최대 10억이다.

그러므로 O(N) 시간으로는 불가능할 것이고, O(logN) 시간으로 풀어야 하겠다는 생각이 들었다.

그렇다면 이진 탐색인데, 이진 탐색을 어떻게 돌아야 할까?

 

그래서 이렇게저렇게 생각을 해보다가, 가장 인접한 두 공유기 사이의 거리를 기준으로 이진 탐색을 하면 되겠다는 생각이 들었다.

그래서, 해당 최대거리를 기준으로 무언가를 비교해서 거리를 이진 탐색하려고 했는데, 무엇을 기준으로 비교를 해야할 지 도저히 생각이 나지 않았다.

 

그래서 결국 풀이를 참고했다.

 

---

풀이 코드

# 2110번: 공유기 설치
n, c = map(int, input().split())

array = []
for _ in range(n):
    array.append(int(input()))

array.sort() # 이진 탐색을 위해 오름차순 정렬

start = array[1] - array[0] # 공유기 사이 거리의 최솟값(첫번째 집에는 무조건 공유기를 설치한다.)
end = array[-1] - array[0] # 공유기 사이 거리의 최댓값
result = 0

while start <= end:
    mid = (start + end) // 2 # 가장 인접한 공유기 사이의 거리
    value = array[0]
    count = 1 # 공유기 설치 개수

    for i in range(1, n): # 앞에서 부터 설치
        if array[i] >= value + mid:
            value = array[i] # 공유기 설치 위치 변경
            count +=1 # 공유기 설치

    if count >= c: # 만약 C개 이상의 공유기를 설치할 수 있는 경우, 가장 인접한 공유기 사이의 거리를 증가
        start = mid + 1
        result = mid # 최적의 결과를 저장
    else: # 만약 C개 이상의 공유기를 설치할 수 없는 경우, 가장 인접한 공유기 사이의 거리를 감소
        end = mid - 1


print(result)

 

아이디어만 잘 생각해낸다면, 풀이 코드 구현은 간단하다.

이런 문제는 파라메트릭 서치 유형의 문제다.

가장 인접한 공유기 사이 거리로 이진 탐색을 돌면 되겠다라는 생각이 들었지만, 이걸 어떻게 비교해야 할지 생각을 하지 못했다.

문제를 많이 풀어봐야 늘 듯하다.