[백준] 2110 공유기 설치(C#)

문제

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

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace dongsik
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            int[] nArr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int num = nArr[0];
            int total = nArr[1];
            
            int[] houses = new int[num];
            for(int i = 0; i < num; i++)
            {
                houses[i] = int.Parse(Console.ReadLine());
            }
            
            Array.Sort(houses);
            
            int start = 1; // 최소 간격
            int end = houses[num-1]; // 최대 간격
            
            while(start <= end)
            {
                int mid = (start + end) / 2;
                
                int cnt = 1; // 설치된 공유기 개수
                int pos = 0; // 공유기 설치한 집
                
                for(int i = 1; i < num; i++)
                {
                    if(houses[i] - houses[pos] >= mid)
                    {
                        cnt++;
                        pos = i;
                    }
                }
                
                if(cnt < total)
                {
                    end = mid - 1;
                }
                else
                {
                    start = mid + 1;
                }
            }
            int result = start - 1;
            Console.Write(result.ToString());
        }
    }
}

고민

이분 탐색으로 풀 생각조차 못했는데, 이분탐색이다.

 

집 간격이 들어오면 정렬해준다.

 

1 2 _ 4 _ _ _ 8 _ 9

 

start는 최소값이니 공유기를 설치할 수 있는 최소간격이다.

최소 1보다 큰 간격으로 설치 할 것이니까 start = 1이된다.

 

end는 최대값인 최대간격을 넣어주면 된다. end = 9

 

그다음엔 간격을 설정해준다. 간격은 mid다

for문을 돌리면서 int mid = (start + end) / 2; 즉, 우리가 임의로 정해둔 간격을 만족하는 집에 공유기를 설치한다.

공유기를 설치했으면 cnt로 공유기 개수를, pos로 마지막으로 설치된 공유기의 위치를 저장해준다.

 

최소값이 최대값과 같아지거나 넘어가면 while문이 멈출거다.

우리가 구할 값은 공유기가 설치된 거리의 최소값을 구하는 문제니까 start - 1을 출력해주면 된다.

만약 최대값을 구한다면 end를 출력해주면 되겠다.