✅ Coding Test
🎈 2110 공유기 설치
집 N개가 수직선 위에 위치해 있고 각 집의 좌표가 x1 ~ xn이다. 이때 공유기 C개를 설치하려 할 때, 최대한 많은 곳에서 와이파이를 사용하려 한다. 한 집에 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려 한다.
결과적으로 C개의 공유기를 N개의 집에 적당히 설치해 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력값으로 첫 줄에 집의 개수 N, 공유기 개수 C이 하나 이상 빈 칸을 사이에 두고 주어진다. 이후 둘째 줄부터 N개 줄에는 집의 좌표를 나타내는 xi가 한 줄에 하나씩 주어진다.
최종적으로 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
import sys
input = sys.stdin.readline
n, c = map(int, input().split())
node = []
for _ in range(n):
node.append(int(input()))
node.sort()
start = 1
end = node[-1] - node[0]
answer = 0
while start <= end:
# 공유기 개수, 설치 위치
cnt = 1
now = node[0]
mid = (start + end) // 2
# 공유기 설치하기
for i in range(1, len(node)):
if node[i] > mid + now:
cnt += 1
now = node[i]
if cnt < c:
end = mid - 1
answer = mid
else:
start = mid + 1
print(answer)< 해설 >
문제의 핵심은 설치해야 할 공유기 개수와 공유기 사이의 최대 거리를 구하는 것.
다음 로직을 가지고 문제를 해결해야 한다.
1. 집 위치를 오름차순으로 sorting하여 일직선 상에 나타낸다.
2. 이후 두 집 사이의 거리를 최소, 최대를 나타내는 변수로 start, end를 지정한다.
3. 첫 집부터 거리가 mid + 현재 공유기 설치 위치보다 먼 곳에 공유기를 설치
4. 설치할 수 있는 공유기 수가 남았다면 거리를 줄여야 함.
ex) 1 2 4 8 9 형태에서, 1, 8 위치에 설치했고 1개의 공유기를 더 설치해야 한다면 1, 8 사이에 있는 집에서 탐색해야 하기에 end를 mid-1로 축소해 탐색 실행
5. 반대로 설치할 공유기 수가 남지 않거나 충족한 경우에는 start를 늘려 범위를 줄여 나간다.
