문제
백준 2110 공유기설치 : https://www.acmicpc.net/problem/2110
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제입력
5 3
1
2
8
4
9
예제출력
3
풀이방법
해당 문제는 이분탐색을 통해서 풀었다. 이분탐색인데 이때 이분탐색의 기준을 공유기 사이의 최소 거리가에 따라 몇 개의 공유기를 최대 설치 할 수 있는가를 기준으로 만들었다.
이때 같은 목표 개수를 설치 할 수 있어도 최대한 거리가 떨어져 있어야 하기에 설치 개수와 목표개수가 같으면 left를 땡겨오는 식으로 이분탐색을 구현했다.
코드
N,C=map(int,input().split(' '))
h=[]
ans=0
def checker(length):
global ans
now=h[0]
count=1
for i in range(1,N):
if(h[i]>=now+length):
now=h[i]
count+=1
return count
for _ in range(N):
h.append(int(input()))
h.sort()
l=1
r=h[-1]-h[0]
while(l<r):
mid=(l+r)//2
if(checker(mid)>=C):
l=mid+1
else:
r=mid
if(C!=2):
print(r-1)
else:
print(r)후기
처음으로 올리는 이분탐색 문제이다. 개인적으로 이분탐색 문제들이 항상 좀 아리송 하다. upperbound lowerbound가 어려운것 같다.
많이 풀어서 유형을 아예 익혀버려야지!
