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

링크

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

난이도(solved.ac 참고)

실버1

풀이

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

 

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

 

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

 

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