문제와 함께 주어진 예시 입력에서도 양끝의 집을 모두 포함하지 않아도 된다는 점은 보셨죠?
그런데
조건에 맞는 집을 고르는 경우의 수 중에서는
양 끝의 집을 모두 포함한 경우가 무조건 존재합니다.
A B C ... X Y Z 와 같이 집이 있을때,
B ... Y 사이의 집을 고르는 것이 정답인 경우가 있다고 가정하면,
이 경우에서 B 와 Y 집을 제외하고 대신 A 와 Z 집을 포함 시키는 경우도 반드시 정답이 되기 때문입니다.
그 이유는 A와 B사이의 거리, Y와 Z사이의 거리가 더 확보되므로 "가장 가까운 두 공유기 사이의 거리의 최대"가 더 작아질 수 없기 때문이구요.
axa1239 4년 전
읽어 주셔서 감사합니다.
저 스스로 궁금증이 해결 되지 않아 글을 작성합니다.
이번 문제에 관하여 공유기 c개를 모두 설치 하되 "가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다." 라고 조건에 문제가 제시 되어 있습니다
이분 탐색 관련 방법으로
왼쪽에서 부터 공유기를 놓고 인접한 공유기를 c개 놓을 수 있는지를 탐색하면서 이분 탐색을 실행 하는 방법으로 코드를 작성 하였습니다
근데 왼쪽이 아니라 가운데 혹은 다른 위치에서 부터 놓는 경우 왼쪽에서 부터 공유기를 설치할 경우 c개를 놓을 수 없지만 가운데 혹은 다른 위치 부터 공유기를 설치 할 경우 c개를 채울수 있는 방법이 존재하지는 않을 까요?
그렇다면 어떻게 확신(?) 증명 할 수 있는지 궁금 합니다.!
글을 읽고 이해가 되지 않았다면 죄송합니다.