[Python] BOJ 2110 - 공유기 설치

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

2110번: 공유기 설치

# 이분탐색 문제이다. (이분탐색 문제는 아이디어 떠올리기가 매우 힘든 것 같다..)

# 집의 좌표가 0부터 10억사이이므로 그 사이에서 이분탐색으로

   '간격' (가장 인접한 두 공유기 사이의 거리)을 찾아가면 된다.

 

import sys
input = sys.stdin.readline
N, C = map(int,input().split())
wifi = []
dab = 0
for _ in range(N):
	wifi.append(int(input()))
wifi.sort()

low, high = 1, wifi[-1] - wifi[0]
while low <= high:
	mid = (low + high) // 2
	# 첫번째 집에 무조건 하나 설치해야 한다.
	cnt = 1
	tmp = wifi[0]

	# 2번째 집부터 확인해가며 tmp + mid보다 좌표가 크면 tmp = 현재 집의 좌표, cnt 1증가
	for i in range(1, N):
		if wifi[i] >= tmp + mid:
			tmp = wifi[i]
			cnt += 1

	# cnt가 C이상이면, 현재 mid를 저장한 뒤 mid를 증가시켜서 더 확인
	if cnt >= C:
		low = mid + 1
		dab = mid
	else:
		high = mid - 1
print(dab)

(solved.ac 티어: 실버 1)

 

 

# 왜 첫번째 집에 무조건 설치해야 하는지는 아래링크에 잘 설명되어있다.

  (실제 문제풀때, 이정도까지 완벽하게 증명할 필요도 없고, 할 수도 없지만

   문제를 많이 풀다보면 수학문제를 봤을때처럼 '감'이나 '느낌'이 생겨서 풀 수 있지 않을까 싶다..)

https://www.acmicpc.net/board/view/31633

글 읽기 - 이분 탐색으로 문제를 풀면 반례가 생길수 있지 않나요?