백준 (BOJ) - 2110 공유기 설치 [Python]

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

2110번: 공유기 설치

이 문제의 중요한 포인트는 역시 공유기 설치하는 거리를 start와 end로 놓는 것이다.

공유기를 설치하는 후보 집과 집 사이의 최소 거리를 start라고 놓고 (최소 길이는 바로 옆에 있는 경우니까 10

최대 거리를 end라고 놓는다 (최대 길이는 첫번째 집 to 마지막집 거리)

처음에 start를 arr[0], end를 arr[-1]이런 식으로 길이가 아닌 좌표로 놓았다가 풀리지 않아 수정하였다.

 

공유기 설치

 

주석으로도 달았듯이 현재 집에서 다음 집까지 거리가, 정해둔 공유기 사이의 거리 (mid)보다 크다면 공유기를 설치 할 수 있다. 

만약 공유기를 설치했다면, 다음 집을 시작 지점인 routerSpot으로 놓고 출발한다.

 

이분 탐색 

 

만약 설치한 공유기 개수를 나타내는 count 변수가 목표 공유기 개수인 C보다 크거나 같다면, 공유기와 공유기 사이 거리를 늘려 설치하는 공유기 개수를 줄여준다. 

import sys 
N,C = list(map(int, sys.stdin.readline().split())) 
arr = []
for i in range(N):
    arr.append(int(sys.stdin.readline()))
arr.sort()
start, end = 1, arr[-1]-arr[0] 
#집과 집 사이 사이의 거리, start : 최소거리 end : 최대거리로
result = 0

while start <= end:
    count = 1
    #설치한 공유기의 개수 
    mid = (start+end)//2
    #공유기 사이의 거리
    routerSpot = arr[0]
    for i in range(1, len(arr)): 
        if  arr[i] >= routerSpot + mid:
#핵심 문장 : 목표지점이 시작점에서 mid만큼 더 한 것보다 멀거나 같으면 그 곳에 공유기를 설치하고 그곳부터 다시 출발한다. 
            count = count + 1
            routerSpot = arr[i] 
#이미 설치한 공유기의 개수가 목표 공유기 개수보다 많으면 공유기 사이 거리를 늘려 공유기 개수를 줄인다. 
    if count >= C:
        start = mid + 1
        result = mid
    else:
        end = mid - 1 
print(result)