출처: https://www.acmicpc.net/problem/2110
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
소스코드
import sys
input = sys.stdin.readline
n, c = map(int, input().strip().split())
arr = [int(input()) for _ in range(n)]
# 간격에 따라 설치 가능한 공유기의 개수를 return하는 함수
def routerCnt(mid):
baseCase = arr[0]
cnt = 1 # 설치할 공유기 수를 담는 변수. 기본적으로 baseCase에 먼저 설치하므로 1에서 시작한다
for i in range(1, n):
if arr[i] - baseCase >= mid: # arr[i] 의 간격이 더 넓으면 설치 가능
cnt += 1
baseCase = arr[i]
return cnt
# 가장 인접한 공유기 사이 최대 거리를 return하는 함수
def BinarySearch(c):
start = 1
end = arr[-1] - arr[0] # 최대 간격은 가장 큰 좌표에서 가장 작은 좌표를 뺀 것
while start <= end:
mid = (start + end) // 2 # mid가 간격이 된다
router = routerCnt(mid)
if router < c: # 이 간격에서 설치되는 공유기의 수가 c보다 작다면
end = mid - 1 # 간격을 좁혀야 한다
elif router >= c: # 크거나 같다면
ans = mid # 정답 후보이므로 ans에 값을 저장해두고
start = mid + 1 # 간격을 넓혀야 한다.
return ans
arr.sort()
print(BinarySearch(c))
풀이
이진 탐색을 응용한 파라메트릭 서치를 이용해서 해결한 문제.
배열의 특정한 값을 찾는 이진 탐색과는 다르게 내가 원하는 조건을 만족하는 알맞은 값을 찾는 것이 파라메트릭 서치이다.
BinarySearch 함수 끝 부분에 router == c 인 경우를 따로 뺐다가 자꾸 런타임 에러가 나서 고민했다.
다른 케이스를 적용해보니 항상 router가 c와 같은 수가 되었을 때 반복문이 끝나는 것이 아니었다.
설치할 수 있는 공유기 개수가 c보다 많더라도 여기서 몇 개를 설치하지 않으면 되기에, router > c 일 때도 답이 될 수 있었고 위와 같은 형태로 풀이를 작성했다.