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

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

2110번: 공유기 설치

이분탐색 문제.

 

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

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

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

 

 

 

	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)

view raw [백준] 공유기 설치.py hosted with ❤ by GitHub