mystika   4달 전

그룹에서 분류가 이분 탐색으로 되어있는 문제들을 풀다가 이 문제를 접하게 되었는데 어떻게 이 문제를 이분 탐색을 이용하여 풀어야 되는지 이해가 잘 가지 않습니다.

N개의 집에 C개의 공유기를 놓아서 가장 가까운 집 사이의 거리를 최대로 늘려놓아야하는데 그러면 C분 탐색으로 풀어야하는게 아닌지..라는 생각이 드는데 아무래도 틀린 접근같아서 이렇게 질문을 올려봅니다.

고수 여러분 도와주세요!

august14   4달 전

"답이 x이상일 수 있는가?"라는 질문에 대답할 수 있다면 어떻게 될까요.
답이 x이상이 아니다 -> 답이 x보다 작은 범위를 탐색
답이 x이상이다 -> 답이 x이상인 범위를 탐색
이므로 이분 검색을 이용해 해결할 수 있습니다.


"답이 x이상일 수 있는가?"라는 질문에 대답은 어떻게 해야 할까요?
가장 왼쪽에 있는 위치부터 순서대로 간격이 x이상이 되도록 공유기를 설치해 보면서 C개 이상을 설치할 수 있는지 보면 됩니다.


sksdong1   4달 전

종만북에도 유사 문제 있는거 같아용

mystika   4달 전

두 분 다 감사합니다! 힌트로 다시 한번 풀어볼께요!

댓글을 작성하려면 로그인해야 합니다.