[BOJ] 2110 - 003

'''
초기 접근
조건 1) 가장 인접한 두 공유기 사이의 거리를 가장 크게 해야 한다.
1. 먼저 주어진 집들 사이의 거리를 오름차순으로 정렬한다.
2. index 0과 n-1을 각각 두었을 때, mid를 구한다.
3. mid가 변화 없을 때 최대 공유기 거리를 구한다.
3. start 또는 end를 변경하면서 최대 공유기의 거리를 구한다.
4. 공유기 간의 거리의 합이 최대가 된다면, 그 거리를 print한다.

도달 과정
1. 가장 인접한 공유기의 거리 최대화
    → start와 end의 오름차순으로 정렬 뒤 고정
        → 두 지점이 가까워지면, 최대가 될 수 없기 떄문
2. mid가 최적 지점 아닌가?
    → 아님. 범위 내 모든 자연수의 나열이 아니라 듬성듬성 숫자가 빠져있기 때문
        → 인접한 거리가 최대가 되어야 함
            → mid와 start, end 거리의 차의 합이 중요치 않다.
3. 그림 그려서 생각해보니 수직선 상에서 mid가 거리차의 합이 최대임
    → 공유기가 3대 이상이라면, 각각의 공유기를 mid로 삼아 설치하면 됨
        → 결국 설치대수인 c를 어떻게 배정하냐가 이 문제의 핵심

소요 시간 : 1시간
결과 : 틀림

이유
1. 문제 파악 너무 늦음
2. 어떤 것을 변수로 두어야 할 지 모름
    → 이게 제일 문제. BS의 개념과 문제를 어떻게 연결시키는지 모른다는 것
3. 구현 시간이 너무 느림
    → 아이디어가 늦어도 구현이 빠르면 여러번 try해서 해결했을 것
'''
import sys
n, c = map(int, sys.stdin.readline().split())
a = []
for i in range(n):
    x = int(sys.stdin.readline())
    a.append(x)
a.sort()

start = 0
end = n-1

while c-3 >= 0:
    mid = (start + end) // 2
    distance_start = a[mid] - a[start]
    distance_end = a[end] - a[mid]
    if c-3 == 0:
        print(min(distance_end, distance_start))
        break
    elif c-3 > 0 and distance_start <= distance_end:
        start = mid + 1
        c -= 1
    elif c-3 > 0 and distance_start > distance_end:
        end = mid - 1
        c -= 1

참고한 코드
https://claude-u.tistory.com/448

import sys
N, C = map(int, (input().split()))
house = [int(sys.stdin.readline()) for _ in range(N)]

#해당 거리를 유지하며 공유기가 몇 개 설치될 수 있는가?
def router_counter(distance):
    count = 1
    cur_house = house[0] #시작점
    for i in range(1, N): #집모두를 돈다
        if cur_house + distance <= house[i]: #이전 집에서 해당 거리보다 멀리 떨어진 집이라면
            count += 1
            cur_house = house[i] #공유기 설치된 집 갱신
    return count

house = sorted(house) #이분탐색을 위한 정렬
start, end = 1, house[-1] - house[0] #1, 첫집과 끝집

while start <= end: #이분탐색 알고리즘
    mid = (start+end) // 2
    
    if router_counter(mid) >= C:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1
        
print(answer)