백준 2110번 : 공유기 설치

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

2110번: 공유기 설치

 

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 N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        long[] arr = new long[N];
        for(int i=0; i<N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(arr);
        
		//lo: 최소간격 1
        long lo = 1;
        //hi: UpperBound로 구해야하기에 '최대로 가질 수 있는 최소간격'을 초과하도록 +1 해줌
        long hi = arr[arr.length-1] - arr[0]+1; 
        long mid = 0;

        while(lo<hi) {
            mid = (lo+hi)/2;
            long lastHouse = arr[0]; //마지막으로 설치되었던 집
            int count = 1; //공유기 설치 횟수

            for(int i=0; i<N; i++) {
                if(arr[i]-lastHouse>=mid) {
                    count++;
                    lastHouse = arr[i];
                }
            }//end for
            
            //설치횟수가 공유기 수 보다 적으면 hi값을 내림 -> 최소간격이 작으면 설치횟수가 늘어나니까
            if(count<C) { 
                hi = mid;
            }
            //설치횟수가 더 많거나 같은경우는 최소간격을 늘리기 위해 lo값을 높임 
            else { 
                lo = mid+1;
            }
            
        }//end while

        System.out.println(lo-1);
	}//end main
}

 

공유기가 마지막으로 설치되었던 집을 기준으로 다음에 설치할 집의 거리를 측정해야한다는 것만 주의를 하면 될 것 같다. 

 

최근 이분탐색 알고리즘을 공부하기 위해 이분탐색에 관한 문제만 골라서 풀고 있다. 이제 문제를 보고 전체적인 흐름은 이해를 할 수 있는데, 세세한 부분에서 자꾸 틀린다(hi값 설정하는 부분, 마지막으로 설치되었던 집을 기준으로 측정해야하는 부분 등..). 좀 더 풀어보면서 익혀야겠다..