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

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

2110번: 공유기 설치

 

[문제]

[풀이]

0번째집 ~ N-1번째 집까지 이분탐색을 통해 interval 값을 이용해 공유기를 설치할 수 있는지 확인하며 interval값을 갱신합니다.

만약 집의 번호들이 1 2 8 4 9 이고 공유기는 3개면, 최대값은 (9-1) / 2 = 4입니다. 만약 1~9가 모두 채워져 있다고 생각하면

1 5 9를 선택할 수 있기 때문입니다.

• home[] 에 N개의 집 위치를 저장합니다.
•  
• 공유기 설치 간격 interval의 최소값과 최대값을 구하여 left, right에 저장합니다.
  • 최소값 1을 left에 저장합니다.
  • 최대값은 (home[N-1] - home[0]) / (C-1) 으로 구하여 right에 저장합니다.
• left와 right의 중간값 mid를 interval로 설정하여 wifi(mid)를 통해 해당 값의 설치 가능 여부를 탐색하여, 설치할 수 있다면 left++하고 없다면 right--를 통해 mid값을 갱신해가며 탐색합니다.

[코드]

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

public class Main {
    static int N;
    static int C;
    static int home[];
    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());
        C = Integer.parseInt(st.nextToken());
        home = new int[N];
        for(int i=0;i<N;i++) {
            home[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(home);
        int start = home[0];
        int end = home[N-1];
        int left = 1;
        int right = (end - start)/(C-1);
        while(left <= right) {
            int mid = (left + right)/2;
            boolean find = wifi(mid);
            if(find) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
    public static boolean wifi(int interval) {
        int cnt = 1;
        int index = 0;
        int now = home[0] + interval;
        while(cnt < C) {
            if(now > home[N-1]) {
                break;
            }
            for(int i=index + 1;i < N;i++) {
                if(home[i] >= now) {
                    cnt++;
                    now = home[i] + interval;
                    index = i;
                }
                if(cnt == C) {
                    return true;
                }
            }
        }
        if(cnt == C) {
            return true;
        }
        return false;
    }
}