문제
도현이의 집 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 = map(int, input().split())
home_pos = []
for i in range(n):
home_pos.append(int(input()))
home_pos.sort() #정렬
combinations = []
#조합 구하기
def getCombinations(li, result, depth):
if depth == c:
combinations.append(result)
else:
for i in range(len(li)):
v = li[i]
temp1 = list(li)
temp2 = list(result)
del temp1[:i+1]
temp2.append(v)
getCombinations(temp1, temp2, depth + 1)
getCombinations(home_pos, [], 0)
#가장 인접한 두 공유기 사이의 거리
distance=-1
for i in combinations:
temp = []
for j in range(len(i)-1):
temp.append(abs(i[j]-i[j+1]))
if min(temp) > distance:
distance = min(temp)
#그 중 최대거리 출력
print(distance)하지만 메모리초과로 인해 고생하다가 이분탐색으로 해결해야 함을 알았다.
이분 탐색(Binary Search)
- 이진 탐색이란 데이터가 정렬돼 있는 배열에서 탐색 범위를 절반식 잘라서 값을 찾아내는 알고리즘이다.
- 데이터가 정렬되어 있어야 사용할 수 있다.
start,mid,end3개의 변수를 통해 이분 탐색을 할 수 있다.
이를 통해서 코드를 짰다.
start와end를 각각 집 사이의 최소거리, 최대거리로 설정한다.- 반복문에서
mid의 값을 설정한다. mid의 거리를 두고 공유기를 설치할 수 있으면start를mid+1위치로 이동한다. 만약 설치할 수 없다면end를mid-1의 위치로 이동한다.- 결과 출력
import sys
#값 입력
n, c = map(int, sys.stdin.readline().split())
home_pos = []
for i in range(n):
home_pos.append(int(sys.stdin.readline()))
home_pos.sort() #정렬
start = 1 #집 사이의 최소거리
end = home_pos[-1] - home_pos[0] #집 사이의 최대거리
result = 0
#이분 탐색
while start <= end:
mid = (start + end) // 2
count = 1 #공유기의 개수
v = home_pos[0] #최소 좌표
for i in home_pos:
if i >= v + mid: #mid만큼 거리를 두고 공유기를 설치할 수 있으면 count ++
v = i
count += 1
#count가 c보다 크면 조건 성립, 거리 늘림
if count >= c:
start = mid + 1
result = mid
#아니라면 거리 좁힘
else:
end = mid - 1
print(result)