문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력5 31 2 8 4 9 |
예제 출력3 |
힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.
풀이
이상하게 그리 어려운 난이도가 아닌데도 해석에 애를 먹었던 문제이다.
이분 탐색을 사용하는 목적을 찾지 못했기 때문인 것 같다.
고군분투 끝에 이해한 것은 공유기를 설치할 거리를 이분 탐색으로 결정한다는 것이다.
중요한 것은 집들이 수직선상에 위치하고 있다는 것을 생각해야 한다는 점이다.
예제와 같이 집들이 수직선상에 있다.
여기서 이분 탐색을 수행하는데, 1 2 4 8 9 목록의 중앙값인 4가 mid가 되는 것이 아니라
집들 사이의 최소 거리와 최대 거리의 중앙인 (1+8)/2 = 4 (몫만 이용) 가 되는 것이다.
마찬가지로 1 2 3 4 10 이라면 mid값은 3이 아닌 (1+9)/2 = 5가 된다.
그리고 이 값을 기준으로 현재 집에서 다음 집의 거리가 mid를 초과한다면 공유기를 설치할 수 있게 된다.
예제에서는 mid가 4이기 때문에 1 다음의 집인 2까지의 거리는 1로, 공유기를 설치할 수 없다.
그 다음의 집은 4인데, 마찬가지로 1 까지의 거리가 3밖에 안되기 때문에 공유기를 설치할 수 없다.
다음인 8까지의 거리는 7로, 4 이상이니 드디어 공유기를 설치할 수 있다!
하지만 그 다음인 9는 8까지의 거리가 1이기 때문에 공유기를 설치할 수 없다.
정리하자면 공유기 설치 간격을 4 라고 할 때, 총 설치할 수 있는 공유기의 개수는 2개이다.
이는 C = 3이라는 예제 조건을 충족하지 못한다. 따라서 공유기의 간격을 좁히면 된다.
만약 간격을 좁힌 뒤 실행한 결과 공유기의 개수가 C를 초과한다면 간격을 다시 넓히면 된다.
위 과정을 이분탐색으로 실행하는 것이다.
import math,sys
input = sys.stdin.readline
n,c = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
start,end = 1, h[n-1] - h[0]
# 집 사이의 최소 거리, 최대 거리
result = 0
if c == 2:
print(h[n-1] - h[0])
# 집이 2개라면 무조건 처음, 마지막 집 사이의 거리
else:
while(start < end):
mid = (start + end)//2
count = 1
ts = h[0]
# 마지막으로 설치된 공유기의 위치
for i in range(n):
if h[i] - ts >= mid:
count+=1
ts = h[i]
if count >= c:
result = mid
start = mid + 1
elif count < c:
end = mid
print(result)
'알고리즘 연습 > 이분 탐색' 카테고리의 다른 글
[🥇2 / 백준 12015 / 파이썬] 가장 긴 증가하는 부분 수열 2 (0) | 2021.07.15 |
---|---|
[🥇3 / 백준 1300 / 파이썬] K 번째 수 (0) | 2021.07.15 |
[🥈3 / 백준 2805 / 파이썬] 나무 자르기 (0) | 2021.07.11 |
[🥈3 / 백준 1654 / 파이썬] 랜선 자르기 (0) | 2021.07.10 |
[🥈4 / 백준 10816 / 파이썬] 숫자 카드 2 (0) | 2021.07.10 |