[Python] 백준 2110번 - 공유기 설치 (골드 4)

혼자 힘으로 풀었는가? X (이해 못함)

알고리즘 분류
 - 이분 탐색
 - 매개 변수 탐색

 

 

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

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, 4, 8, 9] 에서 왜 답이 '3' 인지

 

왜 1, 4, 9 / 1, 4, 8 이 정답이 가능한지

 

일단 위 문제는 가장 인접한 두 공유기 사이의 최대 거리를 구하는 것이다

 

그래서 1, 4의 거리인 3이 정답이 되는 것이었다.

 

import sys

input = sys.stdin.readline

n, c = map(int, input().split())
data = []
for _ in range(n):
    data.append(int(input()))
    
data.sort()

start = 1 # 집 사이의 최소 거리
end = data[-1]-data[0] # 시작 위치에서 끝까지 거리
result = 0
while start <= end:
    mid = (start+end) // 2 # 가장 클 수 있는 거리의 중간 값
    now = data[0] # 첫번째 값 부터 시작
    cnt = 1 # 공유기 개수
    
    for i in range(1, n): # 2번째 집부터 비교
        if data[i] >= now + mid: # data[i]의 위치가 시작값 + 거리보다 크면
            now = data[i] # 현재 위치공유기 설치
            cnt += 1 # 공유기 개수 추가 +1
    
    if cnt >= c: # 공유기 개수가 지정된 개수보다 많으면
        start = mid + 1 # 차이 벌리기
        result = mid
    else: # 더 적게 설치 되었다면
        end = mid - 1 # 거리 줄이기
            
print(result)

 

 

이 문제에서 이분탐색을 쓰는 주체는 '값' 이아닌 '거리' 이다.

 

즉 값인 1과 9 사이의 중간 값인 (1+9)/2 = 5 가 아닌

거리인 최소거리 1과 최대거리 8 (9-1)의 중간 거리인 (1+8)/2 = 4 가 이분탐색을 쓰는 방법이었다.

 

로직을 순서대로 풀자면

 

 

즉 마지막 3) 의 결과에 따라서 공유기 개수는 3개,

최소 거리(s) 는 3+1 = 4, 최대거리(e)는 3 으로 while s <= e 를 위반하여 종료하게 되며

결과값 result = mid = 3 으로 결정된다.

 

문제만 보곤 어떻게 이분탐색을 적용시킬지 어려운 문제였다.