Q29. 안테나 설치
🐣문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
백준 링크 | https://www.acmicpc.net/problem/2110
🐥풀이
가장 인접한 2개 공유기 사이의 거리를 기준으로 이진 탐색 알고리즘을 활용하면 된다.
그럼 start와 end는 어떻게 둬야할까? 공유기 사이의 거리 중 최솟값과 최댓값을 구하면 된다.
공유기는 같은 위치에 설치할 수 없으므로 거리의 최솟값은 1, 최댓값은 가장 끝과 끝의 집 좌표 사이의 거리가 된다. (start=1, end=<가장 먼 두 집 사이의 거리>)
공유기 사이의 거리를 이진탐색으로 정해가며 그 간격으로 설치할 수 있는 공유기의 수를 구한다.
가능한 수가 도현이가 설치할 C개보다 많으면, 결론적으로 C개의 공유기 설치가 가능하므로 한 변수에 저장해두고 간격을 좀 더 넓혀서 이진탐색을 계속 진행한다. (start = mid+1)
적으면, C개의 공유기 설치가 불가능하므로 간격을 좀 더 좁혀서 이진탐색을 계속 진행한다. (end = mid-1)
🐓코드
n, c = map(int, input().split()) # 집, 공유기 개수
house = sorted([int(input()) for _ in range(n)])
start, end, result = 1, house[-1]-house[0], 1 # 최소거리, 최대거리
while start<=end:
mid = (start+end)//2
cur, cnt = house[0], 1 # 현재위치, 공유기 개수
# 한 집씩 최소거리(mid) 이상으로 꽂아가면서 꽂은 공유기 개수 세기
for i in range(1,n):
if house[i]>=cur+mid:
cnt += 1
cur = house[i]
# 공유기 꽂을 개수 c보다 많으면 거리 좀 더 넓혀서 찾아보기
if cnt>=c:
# 공유기 일단 c개 이상 설치 가능하므로 result=mid로 업데이트
start, result = mid+1, mid
# 공유기 꽂을 개수 c보다 적으면 거리 좀 더 좁혀서 찾아보기
else:
end = mid-1
print(result)⭐2022.05.04
어떤 것을 기준으로 두고 이진탐색으로 풀어야 하는 지가 어려웠다 ㅠㅠ 문제 자체도 그냥 봤으면 이진탐색을 바로 떠올리기는 어려웠을 것 같다. "이진탐색"이랑 "공유기 사이의 거리"만 떠올리면 쉽게 풀렸을 문제 같다! (근데 떠올리는 게 어렵지.. ㅠㅠ)
