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

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

2110번: 공유기 설치

문제 풀이

집의 좌표 범위가 10억으로 2중 반복문을 사용하게 되면 시간초과가 발생한다. 따라서 공유기 사이의 최대 거리를 구하기 위해서는 이분탐색을 적용한다.

 

처음 문제를 보고 이분탐색을 통해 공유기 갯수를 구해야 하나 공유기 사이의 거리를 구해야 하나 헷갈려 했었다.

너무 당연한 말이지만 구하고자 하는 값이 공유기 사이의 거리이고 이때 조건이 입력받은 c개만큼의 공유기 갯수가 필요한 것이다.

다시 말해 조건 - 입력받은 c개만큼의 공유기 갯수, 결과 - 공유기 사이의 거리이기 때문에 이분탐색으로 거리를 구해야 하는 것이다.

 

공유기를 C개 만족한다고 하더라도 공유기 간의 거리는 달라질 수 있다. 이때 최댓값을 구해야 하기 때문에 upper bound를 적용한다.

 

거리를 L만큼 주었을 때 설치할 수 있는 공유기 갯수가 cnt이고 조건c 보다 작다면 즉 cnt<c라면 공유기를 더 설치하기 위해 공유이 거리를 줄여야 한다. 따라서 우측 범위를 줄이기 위해 right=mid+1로 설정해준다. 반대 상황도 마찬가지다.

 

코드

package 백준;

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

public class b2110 {
    static int[] houses;
    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 c = Integer.parseInt(st.nextToken());

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

        Arrays.sort(houses);

        int left = 0;
        int right = houses[n - 1] + 1;
        while (left < right) {
            int mid = (left + right) / 2;

            if (putModem(mid) < c) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left - 1);
    }

    /**
     * @param len -> 공유기를 설치할 수 있는 최소거리
     * @return -> 몇 개를 설치할 수 있는지
     */
    static int putModem(int len) {
        int cnt = 1; // 맨 첫 집은 설치했다고 가정
        int lastPutIdx = houses[0]; // house를 정렬해놨기 때문에 최대 거리를 측정하기 위해선 맨 처음 집을 선택

        for (int i = 1; i < houses.length; i++) {
            // 마지막 설치한 위치부터 현재 놓으려는 집 houses간의 거리가 매개변수로 들어온 len의 최소거리보다 큰 경우에만 공유기 설치
            if (houses[i] - lastPutIdx >= len) {
                cnt++;
                lastPutIdx = houses[i];
            }
        }
        return cnt;
    }
}

코드 풀이

이해를 도울 수 있도록 주석으로 설명을 추가해놨다