[백준 2110번] 공유기 설치

난이도: 실버 1

문제 링크: www.acmicpc.net/problem/2110

2110번: 공유기 설치

백준 2110번 공유기 설치

이분 탐색을 이용하는 문제 중 꽤 애를 먹은 문제입니다.

어느 부분에서 이분 탐색을 이용해야 하는지 고민을 많이 했는데,

다른 블로그 (링크)의 글을 참고하여 알고리즘을 이해했습니다.

 

문제의 접근 순서는 다음과 같습니다.

 

1. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건).
2. 집들 사이의 거리를 초기화한다. 최솟값은 1이며, 최댓값은 끝집과 첫집 사이의 거리이다.
3. 집들 사이의 거리를 기준으로 이분 탐색을 진행한다. 주어진 간격 (mid)으로 공유기를 설치했을 때, 주어진 조건을 충족하는지 확인한다.
4. 3번을 만족하는 거리들 중 최댓값을 출력한다.

이분 탐색에 대해 이해하고 계시다면 (모르신다면 클릭), 위 알고리즘을 보시면 코드로 구현하는데 어려움이 없을 것입니다.