[Python] 백준 2110번 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

2110번: 공유기 설치

---

 나의 풀이

C개의 공유기를 N개의 집에 중복없이 설치를 하는데, 가장 인접한 두 공유기 사이의 거리를 최대로 만드는 문제이다. 모든 조합을 nCc개를 하면 제한 속도를 맞추지 못할 것이다. 이분탐색으로 접근해야하고, 이렇게 풀기 위해서는 기준이 필요하다. 이 기준을 찾는게 쉽지않아 다른 사람들의 풀이를 참조하였다. 

경험상 1. array의 인덱스 기준 / 2. array 원소들의 계산값을 기준으로 판단하는 경우가 있는 것 같다. 

여기선 2번 방식으로 공유기의 최소 거리를 늘리는 방향으로 접근했다. 

# 가장 인접 공유기 거리를 설정하고 C개의 공유기가 모두 들어갈 수 있는지 확인한다. 

# 널널하다면 왼쪽 경계선을 mid+1로 올려서 설정하고 반복한다. 

 

# 가장 인접한 두 공유기의 거리를 기준으로 이분탐색을 해보자
import sys

home, route = map(int, sys.stdin.readline().split())
pos = [int(sys.stdin.readline()) for _ in range(home)]
pos.sort()

start = 0
end = pos[-1] - pos[0]
result = 0

while start <= end:
    mid = (start + end)//2
    loc = pos[0]
    count = 1 # 초기값 
    for i in range(1, home): 
        if pos[i] - loc >= mid:
            count += 1
            loc = pos[i]
        else:
            continue
    if count >= route: # 최소 근접거리 mid로 공유기 설치가 가능하다면
        start = mid + 1 # mid를 늘려본다. 
        result = max(result, mid) # 정답에 근접하는 값들이 max값이면 반영한다. 
    else:
        end = mid - 1

print(result)

 

다음에 풀땐 쉽게 풀자

이진 탐색 -> sort 필수!!!

start = worst value
end = best value
result = 결과를 담을 값

while start <= end:
    mid = (start + end)//2
    ```조건 확인```
    if 조건 1:
        start = mid + 1
    else:
        end = mid - 1

print(result)