[BOJ] 2110 공유기 설치

 

가장 인접한 공유기의 최대거리를 이분탐색을 이용해서 구한다는 것까지는 알겠는데 이걸 공유기 C개만큼이 가능한지 확인하는 방법을 생각하기가 어려웠다.

 

해결책을 보니 첫번째 집에 무조건 공유기가 설치된다고 가정하고 계산을 한다.

이건 이해가 아직도 잘 안간다.

 

▶(수정) 거리가 d보다 무조건 같거나 커야하므로 첫번째 집이 아니라 그 다음집부터 시작을 한다면 공유기가 있는 집들간의 거리는 당연히 줄어들 것이다. 그러니까 처음집부터 해야 거리가 좀 더 큰 영역을 확인을 할 가능성을 높일 수 있다.

 

마지막 줄의 답이 x이상일 수 있는가?에 대한 내용을 구현하는 것이 어려웠습니다.
​
정리를 하자면 이렇습니다.
먼저 우린 문제에서 주어진 가장 인접한 공유기 간의 최대거리를 구해야합니다.
​
즉, 공유기를 어디 어디에 설치할지를 탐색해서 구하는 것이 아니라
단순히, 가장 인접한 공유기 간의 최대거리를 찾기 위해 탐색을 하는 것입니다.

 

start = 이전 위치

d = 가장 근접한 공유기의 최대거리 → 나머지 거리는 d보다 같거나 커야한다.

 

a[i] - start >= d

start + d <= a[i]

이전 위치에서 가장 근접한 공유기의 최대거리를 더한 값이 이번 위치보다 크면 안된다. 

그래야 이번 위치를 포함시킬 수 있다. 그렇지 않은데 이번 위치를 포함시키게 되면 거리가 더 짧은 공유기가 존재하는 것이 되기때문이다. 

 

2110번: 공유기 설치

 

백준 알고리즘 2110번 문제풀이