문제:
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력:
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력:
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
from collections import deque
N,C = map(int, sys.stdin.readline().split(" "))
lst = []
for i in range(N):
lst.append(int(sys.stdin.readline()))
lst.sort()
start = 1 # 첫집은 무조건 가야지 최댓값 나올수 있음
end = lst[-1] - lst[0] # 최댓거리
res = 0
while start <= end:
now = lst[0]
count = 1 # 첫집 무조건 설치
mid = (start + end) // 2
for i in range(1,N):
if lst[i] - now >= mid :# 설치해야하는곳
count +=1
now = lst[i] # 다음 공유기 설치한 값으로 옮김 그래야지 그 다음 차이가 mid 보다 크면 설치하기 위해서
if count >= C: # 주어진 갯수 이상 설치하면
if res < mid:
res = mid
start = mid +1
else:
end = mid - 1 # 설치 갯수가 부족하므로, 거리를 줄여준다.
print(res)
처음엔 그냥 짝수개이면 정렬 후 몫 만큼 왼쪽 오른쪽에서 뽑아서 두개 차이 해주고 홀수갯수만 건드려주면 된다고 생각했지만, 홀수개 코드에서 처참하게 무너졌다.
이 문제는 1과 end의 중앙값을 사용해서 와이파이를 설치한다.
설치해야할 갯수보다 공유기를 설치해야하는 집의 갯수가 더 많다면 거리를 늘려준다.
start = mid + 1 : 같더라도 더 최대의 거리가 있을 수 있음으로 거리를 늘려본다 -> start가 커지면 start+end//2의 값이 커짐, 즉 와이파이 거리가 증가한다.
오랜만에 이분탐색은 좀 어려웠다..
댓글