[Python] BOJ(백준) 2110번 - 공유기 설치

1. 링크

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

2. 난이도(solved.ac 참고)

실버1

3. 풀이

	# https://www.acmicpc.net/problem/2110
	import sys
	f = sys.stdin.readline
	n, c = map(int, f().split())
	candidate_list = [int(f()) for _ in range(n)]
	candidate_list.sort()
	start = 1 # 최저 간격인 1
	end = candidate_list[-1] - candidate_list[0] # 최대간격인 끝집 - 첫집
	answer = 0
	while start <= end:
	mid = (start + end) // 2 # 간격들의 중간값
	count = 1 # 일단 하나 설치하고 시작. 맨 앞 집에 설치..
	candidate = candidate_list[0] # 후보지(값 업데이트해주기)
	for i in range(1, n):
	if candidate_list[i] >= candidate + mid: # mid를 더한값보다 더 크다면 공유기 설치해주고 그 위치로 업데이트
	count += 1
	candidate = candidate_list[i]
	if count < c:
	end = mid - 1
	else:
	start = mid + 1
	answer = mid
	print(answer)

view raw 공유기설치.py hosted with ❤ by GitHub

이분 탐색 문제를 풀면서, start와 end를 어떻게 정해야할지가 중요한 부분이라고 생각하게 되었다. 여기서 start와 end는 집의 위치가 아니라 간격의 최소값 최대값으로 하였다.

 

간격이 같아질 때까지 반복하는데, 일단 기본적으로 맨 앞 집에는 설치를 한다고 가정하여 count를 1부터로 놓고 시작하였다. 그리고 기준값(candidate)을 첫번째 집으로 놓고 시작했다.

 

for문을 돌면서(첫번째 집 이후부터 집을 다 돌면서), candidate + mid의 값, 그러니까 기준값에서 중간값을 더한 값보다 그 다음 집이 더 멀다면? 그러면 이 집은 추가를 해줘야한다. 왜냐면 .. 최대거리를 구하는거니까.. 중간값보다 작다면 추가할 이유가 없다. 이렇게 추가를 해주고 기준값을 그 값으로 바꿔준다.

 

for문을 다 돌았는데 설치 대수가 c(공유기의 개수)보다 크다면? 간격을 더 작게 조절해준다. 반대로 작다면 간격을 더 넓혀준다.