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

백준 2110 공유기 설치

이 문제는 풀이를 떠올리지 못했다. N은 200,000으로 N에서 10개를 조합한다고만 고려해도 시간 초과가 난다는 것을 알 수 있었다. 즉, 순차 탐색으로는 풀 수 없다. 이후에 이진 탐색을 떠올렸지만, 이 문제에 어떻게 적용해야 할지 감을 잡을 잡지 못했다.

1. 공유기 사이의 거리를 이진 탐색을 통해 설정하고 설정한 거리를 기준으로 놓았을 때, 모든 공유기를 놓을 수 있는지 확인한다.
2. 기준점과 새로운 집 사이의 거리가 설정한 거리보다 크거나 같다면 놓은 공유기의 숫자를 하나 증가시키고 기준점을 새로운 집으로 업데이트한다.

컨셉 자체가 기발했고, 이분 탐색을 구현하는 과정에서 일반적인 이분 탐색과는 조금 다르게 구현해야 했다. 이 문제에서는 조건을 만족하는 값 중에 최댓값을 찾아야 했다. 즉, 조건을 만족시키는 값을 찾았다고 해서 탐색이 종료되면 안 된다.

if cnt >= c:
    lp = mid + 1
    answer = max(answer, mid)
else:
    rp = mid

• 최댓값을 찾기 위해서 조건을 만족해도 lp = mid + 1을 하여 더 큰 값 중에 만족하는 수가 있는지 확인한다. answer에 최댓값을 업데이트해둔다.

import sys

def binarySearch(lp, rp):
    global answer
    while lp < rp:
        cnt = 1
        mid = (lp + rp) // 2
        ex = houses[0]
        for i in range(1, n):
            if houses[i] - ex >= mid:
                ex = houses[i]
                cnt += 1
        if cnt >= c:
            lp = mid + 1
            answer = max(answer, mid)
        else:
            rp = mid

input = sys.stdin.readline

n, c = map(int, input().split())
houses = sorted([int(input().strip()) for _ in range(n)])
cList = list(range(c - 1)) + [n - 1]

answer = 0
binarySearch(1, (houses[-1] - houses[0]) // (c - 1) + 1)
print(answer)