[Binary Search] Boj2110: 공유기 설치
Link: 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)가 한 줄에 하나씩 주어진다.
출력
- 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
입출력 예제
문제 접근
문제는 총 N개의 집에 C개의 공유기를 놓았을때 공유기들 사이의 거리가 가장 짧은 길이의 최대를 구하고자 한다. 즉, 예제 처럼 1,4,8번 집에 공유기를 놓거나 1,4,9번집에 공유기를 놓으면 3공유기 사이의 거리가 (3,4)와 (3,5)가 된다. 그러므로 공유기를 설치한 두집에 대한 거리들 중 최단 길이를 가장 길게 놓기 위해서 어떻게 구현해야 하는지 찾아야한다.
먼저, 가장 쉬운 방법은 모든 집 사이에 C개의 공유기를 각기 다른 배열로 설치해보면서 가장 큰 최단길이를 구해보는 것이다. 이 방법은 제한시간 2초안에 절대 풀 수 없다.
그러므로 이분 탐색을 이용하여 문제를 풀어야한다. 문제는 C개의 공유기를 설치했을때, 최대 인접 거리가 얼마인지 물었지만, 역으로 생각해보는 것이 좋다.
즉, "어떤 거리(구하고자 하는 답) 만큼 거리를 둘때, 공유기 C개를 설치 할 수 있는 가?" 라고 생각해보는 것이 좋다.
코드
import sys
si = sys.stdin.readline
N,C = list(map(int,si().split()))
house = [0 for _ in range(N)]
for i in range(N):
house[i] = int(si())
house.sort()
#입력받은 거리를 최대로 C개의 공유기 설치가능 여부 확인
def check(distance):
count = 1
last = house[0]
for i in range(1,N):
if house[i] - last < distance: continue
last = house[i]
count += 1
return count >= C
#가장 적합한 거리 구하기
def bs(L,R):
result = R+1
while L <= R:
mid = (L+R)//2
if check(mid):
result = mid
L = mid + 1
else:
R = mid - 1
return result
print(bs(0,house[-1]))스크린샷 및 결과
