2110. 공유기 설치
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
이진 탐색 문제
설치된 공유기 간의 거리를 이진 탐색의 탐색 대상으로 둔다.
어디에 놓을지가 아니라, 얼만큼 떨어진(gap) 곳에 두어야 하는지 결정해야 한다.
집의 좌표를 이진 탐색하는 것이 아니라, 거리를 이진탐색한다.
그래서 시작점과 끝점을 2로 나눈 몫을 먼저 gap으로 둔다.
먼저 첫집을 기준으로 두고, 그 기준에서 gap이상만큼 떨어진 곳을 찾는다.
찾으면 install += 1 을 진행하고, (install => 공유기 설치한 개수)
모든집을 탐색했으면 install 조건을 확인한다.
install >= c : 공유기 설치를 줄일 수 있으므로 gap을 늘린다. 이때 result값을 저장한다(gap을 늘렸을 때, install < c가 되면, result 값이 반환되므로)
install < c : 주어진 개수만큼 설치할 수 없으므로 gap을 좁힌다.
import sys
input = sys.stdin.readline
n, c = map(int, input().split()) # 집, 공유기의 개수
home = [int(input()) for _ in range(n)] # 집의 좌표 입력받기
home.sort()
# 첫집과 끝집
start = 0 # 1도 가능
end = home[-1]
result = 0 # 가장 인접한 두 공유기 사이의 최대 거리
while start <= end: # 이진 탐색 시작
mid = (start + end) // 2 # gap
val = home[0] # 첫번째 집 좌표(시작점)
install = 1
for i in range(1, n): # 모든 집 탐색
if home[i] >= val + mid:
install += 1
val = home[i] # 공유기 설치된 집 갱신
if install >= c: # 설치한 공유기 개수가 c보다 많으면, gap을 늘릴 수 있음.
start = mid + 1
result = mid # result 저장해놓는다.
else: # 설치한 공유기 개수가 c 이하이면 gap을 줄여야 함.
end = mid - 1
print(result)ㅠㅡㅠ 복습해야징 ,, 첫 생각부터 잘못해가지고 찾아봤다
