문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
비록 혼자 힘으로 풀지는 못했지만, 그래도 배운 점이 있다.
우선 이진탐색의 경우, 어떤 구간에 대하여 이진탐색을 할 것인가 가 중요한데 이는 곧 문제에서 출력하도록 요구하는 것일 확률이 높다.
이 문제에서는 가장 인접한 두 공유기 사이의 거리를 요구하고 있기 때문에 거리를 이진탐색의 범위로 잡으면 된다.
그렇다면 이진탐색이 될 수 있는 실질적인 (수치적인) 구간을 어떻게 정할것인지를 생각해보자
이진탐색에는 첫 start와 end가 있고, 이 둘의 중간으로 mid가 정해진다.
첫 최소 거리 (start)의 경우, 문제에서 알 수 있듯, 최소 공유기 개수는 2개이고 집의 좌표는 0 ≤ xi ≤ 1,000,000,000이기 때문에 1로 잡는다.
첫 최대 거리 (end)의 경우, 공유기 간의 거리가, 시작집과 끝 집 간 좌표 거리보다 클 일은 없으므로 이 값으로 지정해주면 된다.
mid는 방금 정한 start와 end의 중간값이다.
이제 loop을 돌면서, 앞집부터 끝집까지 mid 거리를 유지하면서 공유기를 설치해본다.
만약, 설치할 수 있는 개수가 c (설치해야 하는 개수)보다 같거나 크다면, 아직 이 값이 문제에서 요구하는 최댓값인지는 모르지만 정답 후보이기 때문에 저장해두고, 욕심을 내서 mid를 더 크게 잡아본다. (최댓값을 찾기 위해))
만약 설치할 수 있는 개수가 c보다 작다면 mid를 너무 빡빡하게 잡았기 때문에, 이 거리로 문제에서 요구하는 공유기를 설치 못한것이다. 즉, mid (공유기 간의 거리)를 더 작게 해서 다시 시도해봐야 한다.
end가 start보다 같거나 커지면서 이진탐색이 끝나게 되고, 정답 후보가 나올때마다 갱신해 온 answer가 최종 답이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#가장 인접한 공유기 간의 거리가 최댓값이 되게 하라는 것은, 공유기 한 쌍은 엄청 가깝고, 다른 한 쌍은 엄청 먼 경우같이 편향적인 경우를 지양하고
#모든 공유기간의 거리가 최대한 멀도록 optimized된 결과를 도출하라는 것이다.
# n은 집의 개수이고
# c는 공유기의 개수이다
n, c = map(int, input().split())
# address는 집의 좌표를 담은 배열이다.
address = []
for i in range(n):
address.append(int(input()))
# 오름차순으로 변경해준다.
address.sort()
def bs(address, start, end):
#이진탐색이 끝나는 조건
while start <= end:
mid = (start + end) // 2
current = address[0]
#설치할 수 있는 공유기 개수
count = 1
#좌표를 돌면서, 만약
for i in range(1, len(address)):
#current+mid는 현재 거리에서 mid 만큼 떨어진 곳, 그 집에 공유기를 설치할 수 있는지 보는것이다.
#만약 집 좌표가 그 값보다 같거나 크다면 설치할 수 있다는 것임으로, count (설치 가능한 공유기 개수)를 추가해주고, current(현재 위치)를 갱신한다.
if address[i] >= current + mid:
count += 1
current = address[i]
#설치할 수 있는 공유기 개수가 c보다 크면, 간격이 여유가 있다는 뜻임으로, 최대값을 찾기 위해서 거리를 더 넓혀준다.
if count >= c:
global answer
start = mid + 1
#일단 현재값이 답 후보이기 때문에 answer에 저장해준다.
answer = mid
#만약 그 거리만큼 공유기 설치를 할 수 없다면 거리를 줄인다
else:
end = mid - 1
#시작 최소거리는 1이고, 시작 최대거리는 첫 집과 마지막집 간의 거리이다.
start = 1
end = address[-1] - address[0]
answer = 0
bs(address, start, end)
print(answer)