[문제 링크](https://www.acmicpc.net/problem/2110\)

문제 소개

해당 문제는 수직선상의 좌표에서 각 좌표에 몇개의 공유기를 설치했을 때, 인접한 공유기 사이의 최대 거리를 구하는 문제이다.

먼저, 아래와 같이 러프하게 풀었다.

import sys
from itertools import combinations

def solution():
    global N,C
    input = sys.stdin.readline
    N,C = map(int, input().split())
    houses = [int(input().rstrip('\n')) for _ in range(N)]
    houses.sort()
    ans = 0
    for temp in combinations(houses,C):
        li = []
        for t in range(1,C):
            li.append(abs(temp[t]-temp[t-1]))
        ans = max(ans,min(li))
    print(ans)



solution()

당연하게도 시간초과가 발생하였다. 그 이유는 아래와 같다.

• N이 최대 200000인데, 여기에다 combination함수를 돌림
• 참고로 combination함수의 시간 복잡도 O(n! / r! / (n - r)!)임

그럼으로 combination함수로는 문제를 풀기 어렵다. 그리고 xi의 최대 값이 10^9이기 때문에 이 부분을 건들기에는 너무 많다.

이를 해결하기 위해 매개변수 탐색을 생각했다.

매개변수 탐색이란, 간단하게 이분탐색을 하되 특수한 조건에서 진행하는 탐색방법이다. 자세한 것은 아래의 포스팅에 잘 정리해두었다.

매개변수 탐색 참고 링크

아무튼 매개변수 탐색을 진행하기 위해 구하려는 목적과 조건을 아래와 같이 정리하였다.

1. 구하려는 값 : 인접한 공유기 사이의 최대 거리
2. 조건(상황 : 어떠한 공유기 쌍의 최대 거리가 주어졌을 때 이 거리를 충족하는 공유기의 개수를 구했을 때)
   • 만약 공유기 개수가 부족하다면 최대 거리를 줄여야 함 (end = mid - 1)
   • 공유기 개수가 충분하다면 최대 거리를 늘려도 됨 (start = mid + 1)

위의 2번에 부가설명을 하자면, 우리는 어떠한 인접한 공유기 쌍의 거리를 정해두고 이 거리가 성립하는 공유기가 몇개 있는지 확인할 것이다.
이렇게 확인된 공유기의 수가 문제에서 제공하는 공유기 수보다 적을 경우 우리는 어떠한 인접한 공유기 쌍의 거리를 줄여서 공유기 수를 더 많이 확보할 것이다.
반대로, 확인된 공유기의 수가 문제에서 제공하는 공유기 수보다 같거나 클 경우 우리는 이 어떠한 인접한 공유기 쌍의 거리를 최대 거리로 생각해볼수 있다.

그럼으로 위와 같은 방법으로 최대 거리를 구한다. 이해가 안된다면 바로 위의 블럭을 다시 읽어보길 바란다.

최종 코드

import sys


def check(deviceCnt):
    # 어떠한 공유기 쌍의 최대 거리일 때, 만약 공유기 개수가 부족하다면 최대 거리를 줄여야 함 -> end = mid - 1
    # 반대로, 공유기 개수가 충분하다면 최대 거리를 늘려도 됨 -> start = mid + 1
    if deviceCnt < C:
        return True
    return False


def settingDevice(houses, maxDiff, mid):
    deviceDiff, deviceCnt = maxDiff, 1
    nowDevice = houses[0]
    for i in range(1, N):
        if houses[i] - nowDevice >= mid:
            deviceDiff = min(deviceDiff, houses[i] - nowDevice)
            deviceCnt += 1
            nowDevice = houses[i]
    return deviceCnt, deviceDiff


def solution():
    global N, C
    input = sys.stdin.readline
    N, C = map(int, input().split())
    houses = sorted([int(input().rstrip('\n')) for _ in range(N)])

    # 매개변수 탐색, 탐색 대상 : 인접한 공유기 쌍의 최대 거리, 조건 : 공유기 개수

    maxDiff = houses[-1] - houses[0]
    start, end = 1, maxDiff
    ans = 1
    while start <= end:
        mid = (start + end) // 2
        deviceCnt, deviceDiff = settingDevice(houses, maxDiff, mid)
        if check(deviceCnt):
            end = mid - 1
        else:
            ans = max(ans, deviceDiff)
            start = mid + 1

    print(ans)


solution()