백준 알고리즘 - 공유기 설치 (2110) [Python]

문제 www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 상황 - 수직선 위에 존재하는 집들에 공유기를 설치할 때, 최대한 먼 거리에 공유기를 설치하여 그 거리중 가장 가까운 거리를 출력한다. 해결 전략 - 집을 기준으로 잡아서 설치를 시작하면 2분탐색, 3분탐색으로 경우가 무수히 많이 나뉠 수 있다. 이분탐색을 반복하는 구조는 공유기의 개수가 짝수 일 때 문제가 발생한다. 그래서 역으로 최대 거리를 ..
알고리즘 학습/백준 알고리즘 2020. 10. 15. 11:23
1