카테고리: 이분탐색

문제

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

풀이 방식

인접한 두 공유기의 거리를 x라고 가정하고 모든 집에 대해 공유기를 c개 이상 설치할 수 있는지 확인해봅니다. 가능하다면 x보다 작은 값들에 대해서는 공유기를 반드시 c개 이상 설치할 수 있다고 볼 수 있습니다. 만약 x+1의 거리에서 공유기를 모두 설치할 수 없는 상황이 온다면 최대 거리는 x가 될 것입니다. x의 범위는 1부터 10억까지이므로 1부터 찾아가는 방법은 시간초과입니다. 따라서 Parametric Search를 이용하여 문제를 풀어보겠습니다.

1. 조사 거리에 대한 공유기 c개 설치 가능 여부 확인하기

static boolean isTrue(int[] homes, int maxDistance, int c){
	//집 사이 거리가 maxDistanceq이상일때만  공유기를 설치
    int count = 1;
    int leftHome = homes[0];
    for(int i=1; i<homes.length; i++){
    	if(homes[i] - leftHome >= maxDistance){
        	count++;
            leftHome = homes[i];
        }
    }

	return count >= c;
}

2. x의 범위 1부터 10억까지 이분탐색하며 최대값 찾기

최종 코드

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


class Main {

    static boolean isTrue(int[] homes, int maxDistance, int c){
        //집 사이 거리가 maxDistanceq이상일때만  공유기를 설치
        int count = 1;
        int leftHome = homes[0];
        for(int i=1; i<homes.length; i++){
            if(homes[i] - leftHome >= maxDistance){
                count++;
                leftHome = homes[i];
            }
        }

        return count >= c;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

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

        Arrays.sort(homes);

        int start = 1;
        int end = 1000000000;
        int result = 0;

        while(start <= end){
            int mid = (start + end) /2;
            if(isTrue(homes,mid, c)){
                start = mid + 1;
                result = mid;
            }else{
                end = mid -1;
            }
        }

        System.out.println(result);



    }
}