문제 설명
•
개의 집에 개의 공유기를 설치할 때, 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제
예제 입력/출력
•
입력1
5 3
1
2
8
4
9
Plain Text
복사
•
출력1
3
Plain Text
복사
제약 조건
•
•
•
집에 대한 정보
◦
집의 좌표
문제 접근
접근1 브루트 포스
접근2 그리디
접근3 DP -
접근4 파라매트릭 서치 -
풀이 코드
•
파라매트릭 서치 -
import sys
input = lambda: sys.stdin.readline().rstrip()
def is_possible(d):
global arr, N, C
cnt = 1
prev_x = arr[0]
for i in range(1, N):
cur_x = arr[i]
if cur_x - prev_x >= d:
cnt += 1
prev_x = arr[i]
return (cnt >= C)
def parametric_search():
cur = -1
step = int(1e9) + 1
while step != 0:
while (cur + step <= int(1e9)) and is_possible(cur + step):
cur += step
step //= 2
return cur
# Input
N, C = map(int, input().split())
arr = sorted([int(input()) for _ in range(N)])
# Solve
max_dis = parametric_search()
print(max_dis)
Python
복사