백준 2110 <공유기 설치> Python

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

---

매개 변수 탐색 문제입니다.

 

어떠한 규칙에 따라 요소를 배치하고 답을 계산하는게 일반적인 풀이라면 해당 문제는 우선 답을 미리 정해놓고 이 답이 문제에 적합한지 확인하는 풀이 절차를 갖습니다.

 

일반적으로 길이가 L 인 선분 위에 C 개의 점을 배치하되 인접한 점들의 거리의 최솟값이 최대가 되게 하려면 L / (C-1) 이 그 답일 것입니다. 하지만 해당 문제의 경우 점들의 위치 후보군이 정해져 있기 때문에 이러한 방법을 사용하기는 어렵습니다.

 

우선 L // (C-1) 을 인접한 점들의 거리의 최솟값의 최대값이라고 가정 하겠습니다. 어떻게 배치해도 이 값을 넘을 순 없기 때문입니다. 그 뒤 최소 해당 거리만큼 떨어진 점들을 주어진 인덱스 내에서 배치할 수 있는지 확인합니다.

 

배치할 수 있다면 현재 거리는 최댓값의 후보로 두고 조금 값을 높혀 다시 확인하거나

배치할 수 없다면 현재 거리는 후보가 될 수 없으므로 조금 값을 낮춰 다시 확인하는 과정을 거칩니다.

머신러닝에서의 선형 회귀와 비슷한 느낌으로 진행된다고 생각할 수 있습니다.

 

이러한 과정을 일반적으로 이분탐색으로 진행할 수 있겠습니다.

---

import sys
from bisect import bisect_left

input = sys.stdin.readline


# 설정한 값이 가능한지 판단
def is_max_dist(N, C, idxs, max_min_dist):
    # 설치 정보 / [설치 카운트, 설치 위치, 설치 인덱스]
    ins = [1, idxs[0], 0]
    # 앞에서 부터 설치
    while True:
        # 직전 설치 정보
        before_ins_cnt, before_ins, before_ins_idx = ins
        
        # 모두 설치되었으면
        if before_ins_cnt == C:
            return True
        
        # 다음 설치 위치
        next_ins = before_ins + max_min_dist
        # 설치 가능 인덱스
        next_ins_idx = bisect_left(idxs, next_ins)
        # 설치 인덱스가 범위를 벗어나면
        if next_ins_idx >= len(idxs):
            # 중단
            return False
        # 설치 정보 업데이트
        ins = [before_ins_cnt + 1, idxs[next_ins_idx], next_ins_idx]


def solution(N, C, idxs):
    # 인덱스 정렬
    idxs = sorted(idxs)
    # 집 사이의 거리의 최댓값
    max_min_dist = 0
    ## 집 사이의 거리의 최댓값 후보
    # 양 옆 위치
    left = 0
    right = (idxs[-1] - idxs[0]) // (C-1)
    # 간격
    candid_max_min_dist = (right - left)
    # 최댓값을 조정하며 최댓값이 성립하는지 체크
    while left <= right:
        # 최댓값 성립 여부
        is_max = is_max_dist(N, C, idxs, candid_max_min_dist)
        # 해당 최댓값이 성립하면
        if is_max:
            # 최댓값 갱신
            max_min_dist = candid_max_min_dist
            # 왼쪽 위치 상승
            left = candid_max_min_dist + 1
        
        # 해당 최댓값이 성립하지 않으면
        else:
            # 오른쪽 위치 하강
            right = candid_max_min_dist - 1

        # 최댓값 후보 갱신
        candid_max_min_dist = (left + right) // 2

    print(max_min_dist)

    
# 입력
N, C = map(int, input().strip().split())
idxs = [int(input().strip()) for _ in range(N)]

solution(N, C, idxs)