[백준] 2110번: 공유기 설치 Python (이분탐색) | LIM

문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

늘 이분탐색 문제를 접할 때마다 느끼는 거지만 어떤 걸 기준으로 이분탐색을 이용해야 하는지 어렵다.

 

처음 생각한 방식

집의 좌표에 대한 인덱스들로 이분탐색을 진행하는 걸까? 였다. 하지만 여기서 문제는 공유기 개수만큼 어떻게 좌표를 정할 것이냐였다.

문제가 잘 안 풀려서 여기저기 블로그 글을 검색해 보면서 깨달았다.

어떤 부분에서 이분탐색을 이용해야 할지 모르겠을 때는 문제에서 나에게 구하고자 하는 것을 이분탐색 기준으로 두고 풀면 되는구나 하는 인사이트를 얻었다.

따라서 내가 맨 처음 고민한 공유기 개수만큼 좌표를 선택하는 것에 있어서 어디 어디에 설치할 것인지에 대한 정확한 위치는 중요하지 않았던 문제였던 것이다. 

 

문제 풀이 순서

1. 먼저 오름차순으로 정렬한다. (이분탐색에서 정렬은 필수다)

2. 공유기들 사이 거리가 가장 짧은 값을 구한다.

3. 이 거리를 늘려가고 줄이면서(이분탐색을 통해) 공유기를 설치하면서 조건에 맞는 값을 저장한다.

4. 그중 최댓값을 출력한다.