[이코테] 이진 탐색 - 공유기 설치

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

2110번: 공유기 설치

사고과정

• 풀이를 보아도 이해가 단 번에 안가는 문제였다. '이진 탐색'하는 대상을 '집 좌표'라고 생각했는데, 풀이를 보니 가장 인접한 두 공유기 사이의 거리를 탐색하는 문제였다. 보통 주어진 범위 내에서 특정한 조건을 만족하는 가장 큰 값을 찾는 것이 파라메트릭 서치 문제라고 한다. 탐색할 대상을 캐치하고 주어진 조건에 맞춰서 예/아니오 같이 결정문제로 해결하는 문제이다. 예전에 풀었던 떡볶이 떡 문제와 비슷한 유형이라고 한다. 그런데 체감 난이도는 훨씬 높았다..
• 그런데 문제에서 C라는 탐색할 개수를 여러개로 주어지는데, 이를 어찌해야 할지 몰랐다. 보통 1개만 탐색하는 문제를 풀어서 그런지 감이 1도 오지 않았다. 풀이를 보니 첫 번째 공유기를 설치할 집은 고정시키고 C-1개의 공유기를 설치하는 경우의 수를 탐색하면서 가장 인접한 공유기 사이의 거리를 측정했다. 사실 아직도 100% 이해는 안간다.. 계속 반복해서 풀어볼 수 밖에 없을 듯 하다..

풀이(스스로 못 푼 풀이)

import sys

n, c = map(int, input().split())
array = [int(input()) for _ in range(n)]
array.sort()

start = 1                    # 집 좌표 간 최소 거리
end = array[-1] - array[0]   # 집 좌표 간 최대 거리
result = 0                   # 가장 인접한 공유기 간의 거리 기록할 변수

while start <= end:
    mid = (start + end) // 2
    value = array[0]  # 가장 첫번째 집을 고정으로 하고 C-1개 공유기를 설치하는 경우의 수를 탐색하는 것
    count = 1         # 설치한 공유기 개수
    # C-1개의 공유기를 설치하는데, 주어진 첫번째 집 이후의 집들 부터 하나씩 설치
    for i in range(1, n):
        if array[i] >= value + mid:   # value = 찻 반쩨 집 또는 이전에 공유기 설치한 집 -> 이전 집 + 거리보다 먼지 가까운지
            # 해당 집에 공유기 설치
            value = array[i]
            count += 1
    # 설치한 공유기 개수가 주어진 C보다 크거나 같으면 거리 1증가시켜서 확인
    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)