공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

[Python] 백준 2110. 공유기 설치

inspirit941 2020. 2. 13. 17:16
반응형

https://www.acmicpc.net/problem/2110

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

www.acmicpc.net

이분탐색 문제.

 

이분탐색 값의 기준은 '공유기 사이의 거리'이고,

공유기 사이의 거리를 토대로 주어진 문제 조건에 맞게 공유기 개수를 증가시키면서

이분탐색으로 최적의 '공유기 사이의 거리'를 구하는 문제.

 

 

 

import sys
n, c = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
arr.append(int(sys.stdin.readline()))
arr.sort()
start, end = 1, arr[-1] - arr[0]
result = 0
while start <= end:
mid = (start + end) // 2
idx, count = 0, 1
for i in range(1, len(arr)):
# idx 위치에 공유기 설치했을 때 mid 거리 안에 i 위치의 집까지 전파가 닿지 않을 경우
if arr[idx] + mid <= arr[i]:
# 공유기를 하나 추가한다.
count += 1
# 다음 집의 위치에 공유기를 설치한다.
idx = i
# 공유기 개수가 c보다 작을 경우
if count < c:
end = mid - 1
# 공유기 개수가 c보다 클 경우
elif count >= c:
result = mid
start = mid + 1
print(result)
반응형