문제링크

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

구현방법

공유기 c개를 설치 하려함.

한집에 하나만 설치 가능

공유기 사이의 거리를 최대로 하는 경우 찾기

거리에 대한 이분탐색

최대 거리 -> 1번집에서 가장 먼집과의 거리

최소 거리 -> 1

이분탐색으로 거리에 대해서 계산을 진행한다.(이 계산을 진행하기전에 집들의 위치를 정렬을 진행해야함-> 1번집에서 시작해서 계산을 진행해야하기 때문에)

이분탐색으로 값을 뽑은다음 이 값이 문제의 조건에 맞는지 체크하며 조건보다 결과값이 작은 경우

• 너무 멀게 측정해서 공유기가 C개만큼 설치가 안됬기 때문에 max값을 min으로 땡김.

같거나 큰경우

• 너무 가깝게 측정된걸 수도있기 때무에 min 값을 mid +1 값으로 땡김

결과값은 min에서 -1을 한 조건으로 -1의 이유는 현재 min 값은 탐색 값을 초과하는 첫번째 값이기 때문에

알고리즘

이분탐색

CODE

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

public class Main {

    public static int[] house;
    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());

        house = new int[N];

        for(int idx =0; idx <N;idx++){
            house[idx] = Integer.parseInt(br.readLine());
        }

        //정렬
        Arrays.sort(house);

        int min = 1;
        int max = house[N-1] - house[0] +1;

        //핵심로직1
        while(min < max){
            int mid = (max+min)/2;

            //적게 설치됬다는 것은 거리가 너무 멀다.
            if(isPossible(mid) < C){
                max = mid;
            }
            //많거나 같은 경우는 더 설치가 가능할수도있기 때문에 min을 땡긴다.
            else{
                min = mid +1;
            }
        }

        System.out.println(min-1);

    }

    //핵심로직2
    private static int isPossible(int distance) {
        int cnt = 1;
        int lastLocation = house[0];

        for(int idx = 1 ; idx <house.length;idx++){
            int locate = house[idx];

            if(locate - lastLocation >= distance){
                lastLocation = locate;
                cnt+=1;
            }
        }
        return cnt;
    }
}