[BOJ2110] 공유기 설치

1. 문제

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

2. Note

2.1. 알고리즘

"주로, 정답을 구하기는 어려운데 정답을 검증하기 쉬운 경우에 이 알고리즘을 사용하게 됩니다."
https://code.plus/course/5

이분 탐색을 이용한 전형적인 파라매트릭 서치 문제이다. 이전에 푼 <나무 자르기>, <랜선 자르기>와 유사한 문제인데도 풀 지 못했다. 이분 탐색으로 거리를 정하고 검증해 보는 방식인데, 거리 지정부터 검증까지 한 번에 하려고 시도해서 끝까지 해법을 못 찾아낸 듯 싶다. 앞으로 문제를 풀 때도 추상화 된 작은 문제로 분할하여 분석하도록 노력해야 할 것 같다.

2.2. 검증 알고리즘의 유효성

구글링해서 풀이를 살펴보니 모두 첫 번째 집을 기준으로 간격이 주어졌을 때 설치 가능한 공유기 수로 해당 간격이 문제의 조건을 만족하는 지를 검증하고 있었다. 이러한 알고리즘이 왜 유효한가? (https://www.acmicpc.net/board/view/31633)
나는 직관이 부족할 뿐더러 그리디 알고리즘을 증명하는 능력도 부족하다. 많은 문제를 다루며 공부해야 한다고 느꼈다.

3. Reference

• https://www.acmicpc.net/board/view/31633