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

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

2110번: 공유기 설치

풀이

이번 문제는 랜선 자르기, 숫자 카드 등과 같은 이분 탐색 알고리즘 문제이다.

이분 탐색에 대해서 잘 모르거나 이해가 가지 않는다면 위 문제를 먼저 풀어보는 걸 추천한다.

 

이 문제의 목표는 N개의 집이 주어졌을 때 C개의 공유기를 집 간격을 최대한 띄워서 설치하는 것이다.

그렇다면 이분 탐색을 어떻게 적용시켜야할까?

 

이분 탐색에서 중요한 건 바로 기준을 선정하는 것이다.

이 문제에서의 기준은 바로 '집 간의 거리'이다. 집 간의 거리에 따라서 설치할 수 있는 공유기가 달라지기 때문이다.

 

기준이 정해졌으니까 이제 이분 탐색을 이용하면 된다.

초기값은 low는 1, high는 제일 오른쪽에 위치한 집과 왼쪽에 위치한 집의 거리로 하면 된다.

int low = 1;
int high = home[homeCnt-1] - home[0]; 
int ans = 0;
		
while (low <= high) {
    int start = home[0];
    int mid = (low + high) / 2;
    int cnt = 1;
		    
    for (int i=1; i<home.length; i++) {
        if (home[i] - start >= mid) {
            start = home[i];
            cnt++;
        }
    }
		    
    if (cnt >= wifiCnt) {
        low = mid + 1;
        ans = mid;
    } else {
        high = mid - 1;
    }
}

이 문제에서는 이분 탐색을 돌리면서 주의할 점이 있다.

거리를 줄이면 설치가 가능한 공유기 대수가 증가하고, 거리를 늘리면 설치가 가능한 공유기 대수가 줄어든다.

즉, 공유기 대수(cnt)가 목표 공유기 대수(wifiCnt)보다 크거나 같으면 거리가 너무 좁기 때문이므로 low 값을 늘려줘야한다.

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int homeCnt = Integer.parseInt(st.nextToken()); // 집 개수
        int wifiCnt = Integer.parseInt(st.nextToken()); // 공유기 개수
		
        int[] home = new int[homeCnt];
        for (int i=0; i<homeCnt; i++) {
            home[i] = Integer.parseInt(br.readLine());
        }
		
		// 이분 탐색을 위한 정렬 (필수)
        Arrays.sort(home);
		
        int low = 1;
        int high = home[homeCnt-1] - home[0]; 
        int ans = 0;
		
        while (low <= high) {
            int start = home[0];
            int mid = (low + high) / 2;
            int cnt = 1;
		    
            // mid 만큼의 거리에서 설치할 수 있는 공유기 대수
            for (int i=1; i<home.length; i++) {
                if (home[i] - start >= mid) {
                    start = home[i];
                    cnt++;
                }
            }
		    
            if (cnt >= wifiCnt) { // 거리가 좁거나 같은 경우
                low = mid + 1;
                ans = mid;
            } else {              // 거리가 넓은 경우
                high = mid - 1; 
            }
        }
		
        System.out.println(ans);
    }
}