[백준] 2110번 자바 공유기 설치

문제 출처 

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

2110번: 공유기 설치

 

 

 

접근 방식 및 풀이

- 이분탐색으로 거리의 절반을 기준으로 집을 찾아갔다.

- 오늘도 마이구님의 블로그 참고!

https://mygumi.tistory.com/301

백준 2110번 공유기 설치 :: 마이구미

 

 

 

소스 코드 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();

        int[] arr = new int [n];
        for (int i = 0; i <n ; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int left = 1;
        int right = arr[n-1]-arr[0];
        int d = 0;
        int ans = 0;

        while(left <= right){
            int mid= (left + right) /2;
            int start = arr[0];
            int count =1;
            for (int i = 0; i <n ; i++) { //집집마다 검색함.
                d= arr[i]-start;
                if(d >= mid){ //만약 첫번째 집과의 거리가 더 크다면 찾았다고 count 올려주고, 내가 찾는집에 이번 집을 넣어준다.
                    count++;
                    start = arr[i];
                }
            }

            if(count>=c){
                ans = mid;
                left = mid + 1;
            }else{
                right = mid-1;
            }
         }
        System.out.println(ans);
    }
}

 

 

 

 

결과