[JAVA] 백준 2110 공유기 설치

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

2110번: 공유기 설치

 

 

- 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ... ,Xn이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

- 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. 

 

- C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유가 사이의 거리를 최대로 하는 프로그램 

 

 

문제 풀이 

 

[백준] 2110번 : 공유기 설치 - JAVA [자바] (tistory.com)

[백준] 2110번 : 공유기 설치 - JAVA [자바]

 

- 문제에서 주어지는 '설치 해야 할 공유기의 개수(M)'와 같은 거리 중 최대로 가질 수 있는 '최소 거리'를 찾는 것 

- 이전 집과의 거리가 아닌, 직전에 설치를 했던(가장 최근에 설치했던) 집과 현재 집과의 거리를 기준으로 판단해야 함

 

- 거리를 '줄이면' 설치 가능한 공유기 대수가 늘어나고, 거리를 '늘리면' 설치 가능한 공유기 대수가 줄어듬 

0 즉, canInstall 메소드를 통해 얻은 공유기 대수가 M보다 작다면, 거리가 너무 길어서 설치 가능한 대수가 작다는 것

- 그렇기 때문에 hi를 줄이는 것이고, 반대로 M보다 크거나 같다면 거리가 작다는 의미이므로 lo를 좁히는 것 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main 
{
    static int N,M;
    static int house[];
    static int max,min,mid;
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); 
        M= Integer.parseInt(st.nextToken());
        
        house = new int[N];
        
        for(int i=0; i<N; i++)
        {
            house[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(house);
        
        min = 1; //최소 거리가 가질 수 있는 최솟값
        max = house[N-1]- house[0]+1; //최소 거리가 가질 수 있는 최댓값 
        
        while(min<max)
        {
            mid = (min+max)/2;
            
            //mid 거리에 대해 설치 가능한 공유기 개수가 M 개수에 못미치면
            //거리를 좁혀야 하기 때문에 max를 줄임
            
            if(canInstall(mid) < M)
            {
                max = mid;
            }
            else
            {
                //설치 가능한 공유기 개수가 M 개수보다 크거나 같으면 
                //거리를 벌리면서 최소거리가 가질 수 있는 최대거리를 찾아냄ㄴ
                min = mid+1;
            }
        }
        System.out.println(min-1);
    }
    
    //distance에 대해 설치 가능한 공유기 개수를 찾는 메소드 
    static int canInstall(int distance)
    {
        //첫 번째 집은 무조건 설치한다고 가정
        int count = 1;
        int lastLocate = house[0];
        
        for(int i=1; i<house.length; i++)
        {
            int locate = house[i];
            
            /*
            현재 탐색하는 집의 위치와 직전에 설치했던 집의 위치간 거리가
            최소 거리(distance)보다 크거나 같을 때 공유기 설치 개수가 늘려주고
            마지막 설치 위치를 갱신해준다.
            */
            if(locate - lastLocate >=distance)
            {
                count++;
                lastLocate = locate;
                
            }
        }
        return count;
    }
}