문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
요령
입력조건
•
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다
집의 좌표가 10억이라는 큰 범위로 주어졌다. 따라서 해당 문제를 풀기 위해서는 log(n) 알고리즘의 사용이 필요하다.
풀이
•
기본 알고리즘
•
GAP - 현재 설정 간격값
•
Min - 최소 GAP(이진탐색 범위 지정용)
•
Max - 최대 GAP(이진탐색 범위 지정용)
•
prev - 바로 이전에 공유기를 설치한 위치
•
cnt - 현재까지 설치한 공유기의 개수
while Min <= Max
1. GAP = (Min + Max) // 2 (최소 GAP과 최대 GAP의 중간 GAP을 찾는다)
2. array를 탐색하면서 이전 공유기와의 간격이 설정한 N값보다 큰 경우를 찾는다
2.1 cnt++
2.2 prev = 현재 위치
3. array 탐색이 끝났을 때 설치한 공유기 개수(cnt)가 목표치와 비교
3.1 if cnt가 목표치보다 작은 경우 -> (간격이 너무 크다)
MAX = GAP - 1
3.2 else -> 간격이 충분하다(간격 후보 늘릴 수 있음)
result = GAP
MIN = GAP
Python
복사
•
Main 동작
N, C = map(int, input().split()) # 집의 개수, 공유기 개수
arr = list()
for _ in range(N):
arr.append(int(input()))
arr.sort()
left = 1 #최소 GAP
right = arr[-1] - arr[0] #최대 GAP
result = 0 # 정답 GAP을 저장
while left <= right: #이진탐색
mid = (left + right) // 2
prev = arr[0] #제일 처음에 공유기 설치
cnt = 1
for i in range(1, N):
if arr[i] - prev >= mid:
prev = arr[i]
cnt += 1
if cnt < C: # 간격이 너무 커서 공유기 목표만큼 설치 불가 -> 간격 줄이기
right = mid - 1
else:
result = mid
left = mid + 1
print(result)
Python
복사
중요
1.
그냥 mid를 결과로 사용하는 경우 마지막 반복문을 돌면서 정답을 만족하지 못하는 mid값으로 변해버릴 수 있다. —> result를 원하는 조건에 넣어서 저장해주자!
result = mid
left = mid + 1
Python
복사
