[백준/Python] 2110번: 공유기 설치

문제

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

2110번: 공유기 설치

---

문제 요약

도현이의 집 N개가 수직선 위에 있고 공유기 C개를 설치하려고 할 때, 가장 인접한 공유기 사이의 거리의 최댓값을 출력한다.

 

+ 한 집에는 공유기를 하나만 설치할 수 있다.

---

코드

def binSearch():
    global start, end, ans
    while start <= end:
        mid = (start + end) // 2 # 현재 탐색 중인 가장 인접한 두 공유기 사이의 거리
        cur = arr[0] # 공유기를 설치할 수 있는지 탐색 중인 현재 집 (앞 집부터 공유기 설치)
        cnt = 1 # 공유기 설치 개수 (초기: 앞 집에 이미 공유기 설치 됨)

        # 공유기 설치 시작
        for i in range(1, len(arr)):
            if arr[i] >= cur + mid: # 현재 집에서 다음 집의 거리가 mid를 초과하면
                cnt += 1 # 다음 집에 공유기 설치
                cur = arr[i] # 현재 집을 다음 집으로 설정 (다음 집과 다음 다음 집이 공유기를 설치할 수 있는지 확인)
        # 공유기 설치 끝

        if cnt >= c: # 설치한 공유기 수가 c보다 크거나 같다면
            ans = mid # 일단 mid 값 저장
            start = mid + 1 # 가장 인접한 두 공유기 사이의 거리를 늘려도 가능한 경우가 있는지 탐색
        else: # 설치한 공유기 수가 c보다 작다면
            end = mid - 1 # 가장 인접한 두 공유기 사이의 거리를 줄이면 가능한 경우가 있는지 탐색

n, c = map(int, input().split())
# n은 집의 개수, c는 설치할 공유기 개수

arr = []

for _ in range(n):
    arr.append(int(input()))

arr = sorted(arr)

start = 1 # 가장 인접한 두 공유기 사이의 최소 거리 (초기값: 1)
end = arr[-1] - arr[0] # 가장 인접한 두 공유기 사이의 최대 거리 (초기값: 양 끝에 있는 집 사이의 거리)
ans = 0 # 가장 인접한 두 공유기 사이의 거리의 최댓값

binSearch()

print(ans)

---

코드 설명

거리를 이진 탐색을 이용해 찾는다는 점에 유의하자.

 

1. 집의 좌표를 입력 받아 배열 arr에 저장하고, 오름차순으로 정렬한다.

 

2. 가장 인접한 두 공유기 사이의 최소 거리를 이진 탐색으로 찾는다.

 

2 - 1. 두 공유기 사이의 최소 거리를 mid로 설정했을 때, C개의 공유기를 설치할 수 있는지 확인한다.

+ 맨 앞 집부터 공유기를 설치했다고 가정하고 다음 집에 공유기를 설치할 수 있는지 쭉 확인한다.

 

2 - 2. 설치할 수 있는 공유기 수가 C보다 크거나 같으면, mid값을 ans에 저장하고, 가장 인접한 두 공유기 사이의 거리를 늘려도 가능한 경우가 있는지 확인한다.

(start = mid + 1)

 

2 - 3. 설치할 수 있는 공유기 수가 C보다 적으면, 가장 인접한 두 공유기 사이의 거리를 줄이면 가능한 경우가 있는지 확인한다.

(end = mid - 1)

 

3. 탐색이 종료된 뒤 ans값을 출력한다.