백준 알고리즘 - 공유기 설치 (2110) [Python]

 

 

 문제

 

www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

 

 

 

 

 문제 상황

 

- 수직선 위에 존재하는 집들에 공유기를 설치할 때, 최대한 먼 거리에 공유기를 설치하여 그 거리중 가장 가까운 거리를 출력한다.

 

 

 

 

 

 

 해결 전략

 

- 집을 기준으로 잡아서 설치를 시작하면 2분탐색, 3분탐색으로 경우가 무수히 많이 나뉠 수 있다. 이분탐색을 반복하는 구조는 공유기의 개수가 짝수 일 때 문제가 발생한다. 그래서 역으로 최대 거리를 계산하여 하나씩 더해나가며 가능 불가능 여부를 판단해야한다. 즉,

 

집에 공유기를 설치하여 최대거리를 찾는 문제 -> 특정 거리를 두고 설치할 때 설치 가능한지 묻는 문제

 

로 전환하여 생각할 필요가 있다.

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N, C = map(int, input().split())
home = []
for _ in range(N):
    home.append(int(input()))
home.sort()
end = home[-1]-home[0] # 공유기 간 최대 거리
start = 1 # 공유기 간 최소 거리
def setting(distance,C):
    set_point = 0
    C -= 1
    for i in range(1, N):
        if home[i] >= home[set_point]+distance:
            set_point = i
            C -= 1
        if C == 0 : return True
    return False
while start <= end:
    mid = (start+end)//2
    if setting(mid, C): start = mid+1
    else : end = mid-1
print(end)

 

 

 

 

 

 

 

 

 해설

 

- 함수 setting은 특정 거리를 두고 공유기를 설치할 수 있는지 판단하는 함수이다. 이 함수를 이용해 주어진 집들이 거리 mid로 설치가 가능한지 여부를 판단하고 가능하면 mid+1을 하한선으로, 불가능하면 mid-1을 상한선으로 재정의하여 연산을 반복한다.