이진 탐색은 정렬되어 있는 대상을 절반씩 나누어가면 탐색하는 알고리즘이다. 이 문제는 이진 탐색을 통해 N개의 후보 중에 하나의 값을 찾아내어야 하는 문제이다.
1. 공유기 설치
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
2. 문제 해석
이 문제는 간격을 이분탐색해가며 각각의 간격에서 C개 이상의 공유기를 설치할 수 있는지 확인하면서 풀어야 한다.
간격의 될수 있는 후보는 1부터 8(9(끝점)-1(시작점))까지의 정수이다.
1. 처음에는 중간점인 4를 탐색한다.
1) 4가 간격일 때 공유기를 설치할 수 있는 집은 1, 8로 2개이다.
2) 간격이 줄어야 공유기를 더 많이 설치할 수 있으므로 끝점을 3(4(현재설정한 간격)-1)로 지정하고 다시 탐색한다.
2. 1과 3의 중간 지점은 2를 탐색한다.
1) 2가 간격일 때 공유기를 설치할 수 있는 집은 1, 4, 8로 3개이다.
2) 더 큰 간격에서도 공유기를 조건을 만족하도록 공유기를 설치할 수 있는 지 확인하기 위해 시작점을 2(1(현재 시작점)+1)으로 바꾸어 다시 탐색한다.
3. 2와 3의 중간 지점인 2를 탐색한다.
1) 2번과 마찬가지이므로 다시 시작점에 1을 더한다. 시작점: 3(2+1)
4. 3만 남았으므로 3이 조건을 만족하는지 확인한다.
1) 3이 간격일 때 공유기를 설치할 수 있는 집은 1, 4, 8로 3개이다.
모든 조건을 탐색하였으므로 정답은 3이 된다.
3. 풀이
array에 각 집들의 좌표를 받고 정렬한다.(이는 문제를 효율적으로 풀기위함이다. 이진탐색과는 관련 x)
이진탐색의 대상은 gap으로 시작점은 1, 끝점은 입력갑 중 가장 큰 값에서 가장 작은 값을 뺀 것 사이의 정수이다.
n, c = list(map(int, input().split()))
array = []
for _ in range(n):
array.append(int(input()))
array = sorted(array)
start = 1 # gap의 최소치
end = array[-1]-array[0] # gap의 최대치
result = 0
while (start<=end):
cnt = 1 # 첫번째 항으로 하나를 카운트한다.
gap = (end+start)//2 # gap이 될 수 있는 후보중에서 중간으로 시작한다.
value = array[0] # 첫번째 항을 기준 값으로 정한다.
for i in range(1, len(array)): # 첫번째는 먹고 들어갔으니 두번째 항부터 시작한다.
if array[i]>=value+gap: # 정한 gap이후의 값을 만나면,
cnt+=1 # 개수를 추가하고
value= array[i] # 기준 값을 그 값으로 정한다.
if cnt >= c: # 해당하는 gap으로 세어진 개수가 우리가 목표한 값보다 크거나 같으면,
start = gap+1 # 후보군 범위 중 현재 만족하는 gap 위에서 탐색하기 위해 start를 gap+1로 설정한다.
result = gap # 정답의 후보가 되므로 result에 일단 값을 저장한다.
else: # 해당하는 gap으로 세어진 개수가 우리가 목표한 값보다 작으면,
end = gap-1 # 후보군 범위 중 현재 만족하지 않는 gap 아래에서 탐색하기 위해 end를 gap-1로 설정한다.
# 이를 end가 start를 따라잡을 때까지 실시한다.(while)
print(result)