백준 2110번: 공유기 설치

문제

• https://www.acmicpc.net/problem/2110
• N개 중 C개를 선택한 조합들 중 최적의 조합을 이진 탐색 방식으로 찾기

기록 포인트

• 이진 탐색을 적용해 풀이하는 과정
• 접근법의 상세한 내용은 아래 링크 참고
  • 백준 2805번 문제 풀이

접근 방식

• 탐색 과제 접근법 적용
  • 탐색 목표: 집과 집 사이의 거리가 최대가 되었을 때의 거리
  • 탐색 대상: 집과 집 사이의 거리(d)
  • 모든 경우의 수: d의 최소값(1) ~ d의 최대값(첫번째집부터 마지막집까지의 거리)
  • 선형 탐색 과정
    • d를 최대값부터 최소값까지 1씩 줄이며 조건이 충족될 때 탐색 종료
    • 선형 탐색 종료 조건: d보다 크거나 같은 간격으로 C개의 집을 선택 가능할 때
  • 선형성 파악
    • d1 > d2 일 때, d1가 조건을 충족하면 d2도 무조건 충족
      • 가령, 거리 3으로 간격 설정에 성공하면, 거리 1,2는 무조건 성공
    • d1 < d2 일 때, d1가 조건을 충족하지 못하면 d2도 무조건 충족 불가
      • 가령, 거리 5로 간격 설정에 실패하면, 거리 6 이상은 무조건 실패
  • 이진 탐색으로 변형
    • 초기 설정
      • left, right 각각 d의 최소값, 최대값
      • 정답의 초기값은 최소값 (d의 최대값을 찾는 것이 목표이므로)
    • 이진 탐색 진행
      • 탐색 종료 시점은 탐색 범위가 더 이상 없을 때
        • left > right
      • 탐색 범위의 중앙값으로 조건 충족 여부 판단
        • mid는 left와 right의 중앙값
        • 조건 충족: mid보다 크거나 같은 간격으로 C개의 집 선택하기 성공
      • d보다 크거나 같은 간격으로 C개의 집 선택하기에 성공하면
        • 조건 충족으로 최적값 업데이트
        • mid보다 작은 값은 탐색할 필요 없음
      • d보다 크거나 같은 간격으로 C개의 집 선택하기에 실패하면
        • 조건 미달
        • mid보다 큰 값은 탐색할 필요 없음

제출 답안

• 첫 번째 집에 1개를 설치한 뒤 나머지 집들에 d이상의 간격으로 C-1개를 설치
  • 조건 충족 판단 시 C-1로 시작

import sys
sys.setrecursionlimit(10**6)
N, C = list(map(int, sys.stdin.readline().split()))
houses = []
for i in range(N):
    h = int(sys.stdin.readline())
    houses.append(h)

# 집들 정렬
houses.sort()

# 조건 충족 판단 함수
#   집들에 C개의 공유기를 거리 d 이상으로 설치 가능한지 여부를 재귀적으로 판단
def select_house(start_index, d, C):
    # 더 이상 설치할 필요 없으면 성공
    if C == 0:
        return True
    # 1개를 설치 가능한지 판단
    base = houses[start_index]
    for i in range(start_index+1, len(houses)):
        diff = houses[i] - base
        # 설치 가능하면 현재 위치를 기점으로 삼아 다음 설치로 이동
        if diff >= d: 
            return select_house(i, d, C-1)
    # 설치 불가능하면 실패
    return False

# 탐색 범위 설정
left, right = 1, houses[-1] - houses[0]
answer = left
while left <= right:
    mid = (left + right)//2
    condition = select_house(0, mid, C-1)
    if condition:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1

# 정답 출력
print(answer)