문제 출처 : https://www.acmicpc.net/problem/2110
문제 정리
- 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
- 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
- C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
문제 해결 방법
그리디 문제라고 생각해서 20분 정도를 고민하다가 못풀어서 다른 블로그를 참고했다..
→ 참고한 블로그
물론 참고해도 이해를 못하다가 시간이 좀 지나서 이분 탐색 문제라는 것을 알았다.
“여전히 이분 탐색 문제는 아무리 봐도 이분 탐색 문제인지 파악하는 것 자체가 굉장히 힘들다.”
정말 간단하게 풀이 방법을 설명하겠다.
-
먼저 가장 첫번째 집에는 공유기를 설치한다.
- 왜냐면 인접한 공유기의 거리가 최대가 되게 하려면 가장 처음을 기준으로 공유기를 설치해야하기 때문이다.
-
이분 탐색을 활용해서 첫 번째 집 좌표와 마지막 집 좌표 사이에서 이분 탐색을 진행한다.
→ 이분탐색
- 예를 들어, 문제의 주어진 예시의 정답은 3이다. 즉, 공유기 사이의 거리의 최대값 중에 최소값을 3이라고 볼 수 있다.
- 만약 공유기 사이의 거리를 3보다 크게 잡았는데 입력 받은 공유기의 개수보다 작다면 오른쪽에서 줄여야한다.
- 만약 공유기 사이의 거리를 3보다 작게 잡았는데 입력 받은 공유기의 개수보다 크거나 같아면 왼쪽에서 늘려야한다.
코드