인접한 두 공유기 사이의 최대 거리가 L이다. 라고 가정해 봅시다. 집이 n개 있고요.

그렇다면, n은 상수이지만, L이라는 것은 범위가 변할 수 있단 말이지요.

왜 x축 좌표가 제일 작은, 첫 번째 집부터 설치해 보느냐. 이유는 간단합니다.

x축으로 정렬했을 때, x[1], ... , x[n]인 집들이 있다고 해 봅시다. 단 임의의 i<j에 대해, x[i]<=x[j]겠죠. (a)

x[1]에 설치했다고 가정해 볼까요?

x[1] + L이상인 최초의 지점이 q라고 해 봅시다. 즉, x[1] + L <= x[q]이고, x[q-1] < x[1]+L인 셈이죠. (b)

이 경우, q의 위치부터 설치할 수 있습니다.

문제는 x[2]에 설치한 경우인데요.

x[1] + L <= x[2] + L입니다. (c)

그렇다면, x[2] + L이상인 최초의 지점이 t일 때, q<=t일 수 밖에 없습니다. 왜냐면, x[1] <= x[2]이기 때문입니다.

이 부분은 (a), (b), (c)를 이용해서 증명해 보세요.

굵은색으로 칠한 명제를 일반화 시킨다면.

최대한 왼쪽에 설치할수록, 그 다음 공유기는 왼쪽에 설치할 수 있고. 더 많이 설치할 수 있게 됩니다.

Hint.

x 좌표 오름차순으로 정렬이 되어 있다면

1<=u<t<=n이면, x[u]<=x[t]이고, 그 역도 성립한다는 것을 이용해 보세요.

아. 역은 성립 안 하겠구나.. 1<=u<=t<=n이면 x[u]<=x[t]이다..는 성립하겠다만..

암튼. 그 친구를 증명하신다면

L이라는 친구가 커질수록 설치할 수 있는 공유기의 갯수가 작아진다는 것 또한 증명할 수 있습니다.

L1<L2라고 한다면

x[1] + L1 = u<t = x[1] + L2라고 놓으시고, 천천히 대치법으로 증명해 보시면 좋을 듯 싶습니다.

f(L)을 가장 인접한 두 공유기의 거리가 L일 때, 설치할 수 있는 최대 공유기 갯수라고 한다면

f(x)는, x가 커짐에 따라 단조 증가, 혹은 단조 감소 함수이므로 이분 탐색을 적용할 수 있습니다.

chogahui05님 !  친절한 설명 감사드립니다! 덕분에 이해가 됬습니다!!