BOJ 2110 - 공유기 설치 문제

문제

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

2110번: 공유기 설치

 

 

 

문제 접근

• 이분 탐색의 유형인데 주어진 집의 데이터를 가지고 이분 탐색을 진행하는 것이 아니다. 문제에선 두 공유기 사이의 최대 거리를 요구하고 있기 때문에 이분 탐색으로서 우리가 찾아야 하는 값은 바로 두 공유기 사이의 최대 거리이다.
• 따라서 가장 작은 범위는 각 집마다 공유기를 한 개씩 설치함으로서 얻어지는 0이 되며, 가장 큰 범위는 첫 번째 집부터 마지막 집까지의 거리로 이는 0에서 가장 가까운 집의 위치와 가장 먼 집의 위치의 차가 될 것이다.
• 이를 수행한 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] house;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int 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);

        int front = 1;
        int end = house[N - 1] - house[0] + 1;

        while(front < end){
            int mid = (front + end) / 2;

            // 설치한 공유기 개수가 있는 공유기 개수보다 적다면 더 적은 반경으로 해도 된다.
            if (getInstallCnt(mid) < M){
                end = mid;
            } else{
                front = mid + 1;
            }
        }

        System.out.println(front - 1);
    }
}

• 이제 우리가 생각해야 하는 것은 해당 범위를 가정한 체로 공유기를 설치할 경우에 몇 개를 설치할 수 있을것인가라는 것이다.
• 만약 현재 있는 공유기보다 더 많이 설치해야 한다면 공유기의 개수를 줄여야 하므로 범위를 늘려야 한다.
• 만약 현재 있는 공유기보다 더 적게 설치해야 한다면 공유기의 개수를 늘려야 하므로 범위를 좁혀야 한다.
• 그렇다면 몇 개를 설치할 수 있는가에 대한 함수를 작성해야 한다. 설치를 하기 위해서는 거리를 알아야 한다. 그렇다면 입력으로 거리를 받은 뒤 가장 최근에 설치한 위치와 현재 위치의 차이를 계산해 설치해야 할 거리인지를 확인하고, 설치해야할 거리라면 설치를 한 뒤 설치 개수를 1개 늘리면서 직전에 설치한 위치를 갱신하는 방식으로 구현할 수 있다.

static int getInstallCnt(int dist){
    int cnt = 1;
    int prevInstallLocation = house[0];

    for (int i = 1; i < house.length; i++){
        int location = house[i];

        if (location - prevInstallLocation >= dist){
            cnt++;
            prevInstallLocation = house[i];
        }
    }

    return cnt;
}

• 전체적인 답안 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class StudyCode {
    static int[] house;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int 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);

        int front = 1;
        int end = house[N - 1] - house[0] + 1;

        while(front < end){
            int mid = (front + end) / 2;

            // 설치한 공유기 개수가 있는 공유기 개수보다 적다면 더 적은 반경으로 해도 된다.
            if (getInstallCnt(mid) < M){
                end = mid;
            } else{
                front = mid + 1;
            }
        }

        System.out.println(front - 1);
    }

    // 해당 와이파이 범위만큼 조정한 상태에서 설치를 한다면 몇 개를 설치할 수 있는가를 구하는 메서드
    static int getInstallCnt(int dist){
        int cnt = 1;
        int prevInstallLocation = house[0];

        for (int i = 1; i < house.length; i++){
            int location = house[i];

            if (location - prevInstallLocation >= dist){
                cnt++;
                prevInstallLocation = house[i];
            }
        }

        return cnt;
    }
}