[C#]백준/공유기 설치/이진 탐색

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
 
        int houseCount = int.Parse(input[0]);
        int routerCount = int.Parse(input[1]);
 
        List<int> xList = new List<int>(houseCount);
 
        string inputLine;
 
        while ((inputLine = Console.ReadLine()) != null)
            xList.Add(int.Parse(inputLine));
 
        //집의 좌표를 정렬한다.
        xList.Sort();
 
        //이진 탐색을 위한 초기 설정
        int left = 1;
        int right = xList[houseCount - 1] - xList[0];
        int maxDistance = int.MinValue;
 
        //이진 탐색을 수행한다.
        while (left <= right)
        {
            //현재 검사하는 공유기 사이의 거리
            int currentDistance = left + (right - left) / 2;
 
            //installedRouters는 현재 검사하는 거리로 설치할 수 있는 공유기의 개수.
            int installedRouters = 1;
 
            //prevRouter는 이전에 설치한 공유기의 좌표.
            //for문 돌며 갱신
            int prevRouter = xList[0];
 
            //공유기를 설치할 수 있는지 확인한다.
            for (int i = 1; i < houseCount; i++)
            {
                //현재 집과 이전에 설치한 공유기 사이의 거리가 mid 이상인 경우 공유기를 설치한다.
                if (xList[i] - prevRouter >= currentDistance)
                {
                    installedRouters++;
                    prevRouter = xList[i];
                }
            }
 
            //공유기를 충분히 설치할 수 있는 경우, 거리를 늘린다.
            //거리를 늘리는 것은 설치할 수 있는 공유기 사이의 최대 거리를 찾기 위함이다.
            if (installedRouters >= routerCount)
            {
                maxDistance = currentDistance;
                left = currentDistance + 1;
            }
            //공유기를 충분히 설치할 수 없는 경우, 거리를 줄인다.
            //거리를 줄이는 것은 공유기를 더 설치할 수 있는 범위를 찾기 위함이다.
            else
            {
                right = currentDistance - 1;
            }
        }
 
        Console.WriteLine(maxDistance);
    }
 
}