백준 2110 공유기 설치
-
백준 2110 공유기 설치Algorithm/BOJ 2021. 3. 3. 20:52
출처: www.acmicpc.net/problem/2110 분류: 이분 탐색 접근방식 이분 탐색 문제인 걸 알고 접근했는데도 접근이 어려웠던 문제였습니다. ㅠㅠ 이녀석 쉬워지질 않네요... 공유기들의 위치가 주어지기 때문에 이걸 가지고 어떻게 이분탐색을 해야하나 싶지만, 저희는 공유기 사이의 거리가 가장 큰 경우를 찾아야 합니다. 따라서 공유기 사이의 거리를 가지고 이분 탐색을 돌려야 합니다. 따라서 저희는 최소 설치 거리를 low 최대 설치 거리를 high 정해서 이분탐색을 해야합니다. 다음에는 해당 거리를 최소 간격으로 해서 공유기를 설치할 수 있는지 없는지만 체크해주면 됩니다. 이건 일단 나중에 생각해보죠 :( 자 그럼 공유기 사이의 거리가 가장 짧은 경우는 어떤 경우일까요? 바로 옆집에 공유기를 ..