문제
접근
문제 접근은 n의 개수와 좌표의 범위를 봤을 때 이분탐색을 사용해야 한다.
그렇다면 어떤 것으로 이분탐색을 해야할까?
얼핏 봤을땐 공유기를 어떤 집에 배치해야 하는지가 중요해보여서 집을 이용해서 이분탐색을 생각할 수도 있다.
하지만 문제의 핵심은 공유기 사이의 최대 거리를 구하는 문제이다.
공유기 사이의 거리는 값의 범위가 명확하고 구하고자 하는 문제와 동일하다.
즉, 공유기 사이의 거리를 최소와 최대를 정하여 이분탐색한다면 이분탐색의 결과가 곧 정답이다.
우선 주어진 배열을 정렬하자.
그리고 최대와 최소를 정해야한다.
거리의 최소는 당연히 1이 될 것이다.
최대의 경우 정렬된 배열에서 양끝값을 빼주면 최대이다.
이제 최소에서 최대 사이에서 이분탐색을 진행하면 된다.
이분탐색 과정에서 특정 거리 x가 문제의 조건을 만족하는지 확인해야 한다.
즉, 어떤 거리 x(여기서는 mid)가 문제에서 주어진 공유기의 개수를 모두 설치했을 때 가능한 간격이 맞는지 확인해야 한다.
이 부분은 그냥 정렬된 배열을 한바퀴돌면서 확인하도록 했다.
이렇게 구현하면 시간복잡도는 가능한지 조건을 검사하는데 O(N)
그리고 이분탐색을 진행하는데, 계산이 잘안된다 최대가 O(log 10억) 이면 한 30정도 되지 않을까?
거의 상수 시간안에 해결이 가능할 거 같으니 대충 O(N) 정도 걸린다.
코드
- 파이썬 코드
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
import sys
input = sys.stdin.readline
def binarySearch(arr, c):
start = 1
end = arr[-1] - arr[0]
answer = 0
while start <= end:
mid = (start+end) // 2
if isSettingPossible(arr, mid, c):
start = mid + 1
answer = max(answer, mid)
else:
end = mid - 1
return answer
def isSettingPossible(arr, distance, c):
before = arr[0]
settingEqip = 1
for item in arr:
if item - before >= distance:
settingEqip += 1
before = item
if settingEqip < c:
return False
else:
return True
if __name__ == "__main__":
n, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.sort()
answer = binarySearch(arr, c)
print(answer)