[BOJ_Python] 2110.공유기 설치

문제

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

 

사용 알고리즘

이분탐색

 

풀이

고려사항

1. 가장 인접한 거리 확인하기

 

후기

1. 이 문제의 keypoint는 이미 설치 후 거리를 확인하는 것이 아니라,

거리를 먼저 설정하고 그 거리보다 멀리 몇 개의 공유기가 설치 될 수 있는지를 확인하는 것이다.

먼저 공유기를 설치 후 진행하게 되면 확인 해야 할 범위가 큰 경우 시간초과가 발생한다.

때문에 이분탐색을 통해 거리를 먼저 설정 후 공유기 설치 가능 갯수를 확인하며

거리의 범위를 조절해 가는 것이 효율적이다.

2. 이때 최대한 최적화를 시키기 위해 end의 범위도 변경해주었다.

원래는 max값을 기준으로 설정하여 진행하지만,

여기서의 max 값은 마지막 집이 아니라 마지막 집에서 첫 집의 거리를 뺀 총 거리에서 C-1을 나누어 주었다.

이는 균등하게 설치하였을때의 값으로 

집이 촘촘하게 모두 있을 때의 최대 값이다.

하지만, 모두 촘촘하게 존재하지 않으므로 이 값을 기준으로 최대값을 줄여나가는 방식을 선택하였다.

3. 이후 코드의 흐름은 이분탐색의 기초 토대로 진행되었다.

mid값을 통해 거리의 기준을 잡고 공유기 설치 갯수를 확인하며 거리를 조정해주는 방식이다.

 

코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
house = list(int(input()) for _ in range(N))
house.sort()

start, end = 1, (house[-1] - house[0]) // (C - 1)
while start <= end:
    mid = (start + end) // 2
    cur = house[0]
    cnt = 0
    for i in house:
        if i - cur >= mid:
            cnt += 1
            cur = i
            if cnt >= C - 1:
                break

    if cnt >= C - 1:
        start = mid + 1
    else:
        end = mid - 1

print(end)

 

결과