[BOJ/JAVA] 2110번: 공유기 설치

2110번: 공유기 설치

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

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

키워드

• 집에 공유기 C개를 설치

• 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치

---

구현

• huses[]
  • 각 집의 좌표를 오름차순으로 정렬한다.

• solution()
  • 인접한 두 공유기 사이의 거리를 매개변수로 이분탐색을 진행한다.
    • 초기 low는 1
    • 초기 high는 마지막원소 - 첫번째 원소 (이 때가 차이가 가장 크므로..)
    • [low, high]에 속하면서, mid = (low+high)/2 간격으로 공유기를 설치할 수 있는지 체크한다.

• check()
  • mid 간격으로 공유기를 설치하는 방법
  • houses[0]값은 무조건 선택한다.
  • prePos
    • 이전에 선택된 공유기의 좌표를 저장한다.
  • 간격이 mid 이상이면 현재 위치에 공유기를 설치한다.
  • 공유기의 설치 횟수가 C면 true값을 반환한다.
  • 반복문이 종료되면 false를 반환한다.

---

코드

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

public class java_2110 {
    static int N, C;
    static int houses[];

    // mid 크기로 만들 수 있는가?
    static boolean check(int mid) {
        boolean result = false;

        //
        int prePos = houses[0];
        int count = 1;
        for (int i = 1; i < N; i++) {
            if (houses[i] - prePos >= mid) {
                prePos = houses[i];
                count++;
                //
                if (count == C) {
                    return true;
                }
            }
        }

        return result;
    }

    static int solution() {

        Arrays.sort(houses);

        int low = 1;
        int high = houses[N - 1] - houses[0];

        while (low <= high) {
            int mid = (low + high) / 2;

            // mid로 만들 수 있는가? -> 더 넓은 크기로 만들어보자
            if (check(mid)) {
                low = mid+1;
                continue;
            }

            // -> 더 좁은 크기로 만들어보자
            high = mid-1;
        }

        return high;
    }

    public static void main(String[] args) throws IOException {
        // 집에 공유기 C개 설치
        // 한 집에 공유기 하나만 설치 가능
        // 두 공유기 사이의 거리를 가능한 크게
        // 1 2 4 8 9

        // 범위 = 가장 작은 x값, 그 다음 작은 x값, 가장 큰 x값
        // 해당 거리가 최소가 되도록 설치가 가능한가?

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        houses = new int[N];
        for (int i = 0; i < N; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }

        int result = solution();

        System.out.println(result);

        br.close();

    }
}

---

Uploaded by N2T