[백준] 2110번 공유기 설치 - 파이썬

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

2110번: 공유기 설치

풀이

알고리즘은 이진탐색으로 문제를 풀어야 시간초과가 걸리지않는 문제이다.

목표는 공유기를 설치한 집들 중 가장 가까운 집들의 거리의 최대값을 구하는 문제이다.

 

우선 가볍게 생각해보자 x좌표가 1인 집에서 간격이 5인 집의 x좌표는 몇일까? 당연히 6이다.

이 당연한 논리를 가지고 문제를 풀어볼 것이다.

간격을 이진탐색으로 선택하여 값의 조건을 만족하는 x의 최소간격을 찾을 것이다.

 

C = 설치할 수 있는 공유기의 개수

대신 cnt를 둬서 C보다 많은 공유기를 설치할 수 있다면 간격의 범위를 더 크게 둬서 간격을 최대한 키워준다. 설치할 수 있는 공유기의 개수보다 적은 공유기를 설치할 수 있다면 간격을 줄여 C이상이 될 수 있게 바꿔준다.

 

 

# 2110번 공유기 설치
# 수직선 위에서 이뤄진다. N: 집 개수, C: 공유기 개수
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
arr = []
for i in range(N):
    arr.append(int(input()))

arr.sort()

start = 1                    # 집과 집사이가 인접할 수 있는 최소거리(주어진 집들 중에 1차이 나는 집들이어도 상관x)
end = arr[-1] - arr[0]       # 주어진 집들의 위치에서 인접할 수 있는 최대거리
answer = 0

while start <= end:              # 공유기를 배치할 거리를 알아낼 for문 교차 시 중지.
    mid = (start + end) // 2
    cnt = 1                      # 어떠한 간격으로 공유기를 설치를 할 수 있는 공유기 개수(앞 집은 설치하고 시작한다 +1)
    current = arr[0]             # 앞 집부터 설치
    for i in range(1, len(arr)):
        if arr[i] >= mid + current:   # 주어진 간격만큼 차이나는 집이 몇개가 있는지 확인중.
            cnt += 1
            current = arr[i]

    if cnt >= C:    # 주어진 간격으로는 빽빽하게 설치가 가능하거나 너무 널널할 경우 이전의 간격 초과로 범위를 줄여준다.
        start = mid + 1
        answer = mid
    else:               # 주어진 간격으로는 설치 할 수 없는 경우 이전의 간격 미만으로 범위를 줄여준다
        end = mid - 1
print(answer)