알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-2110(공유기 설치)

By on October 13, 2019

문제

문제 링크 : 이분탐색-공유기 설치 https://www.acmicpc.net/problem/2110

이분탐색 공유기 설치 문제

풀이

  • 이 문제는 어떻게 이분 탐색으로 접근을 해야 할지 한참을 생각 해야 했다.

    첫번째로 주어진 갯수 만큼 공유기를 설치해야 하고.
    두번째로 공유기가 설치 된 집간의 거리를 구해서 거리를 측정해야한다…

    문제를 해결 할 수 있었던 방법은 이분탐색의 mid 값을 집간의 거리 로 생각 하고 로직을 구현 하였다.

  • 풀이 시작

    • 주어진 집의 위치를 배열에 담는다. (int[] location)

    • 이분 탐색할 범위는 1 ~ 가장 마지막 집 까지 설정 한다.

    • mid 를 집간의 거리로 생각 하자.

      • 우선 첫번째 집에 설치.
      • 첫번째 집에서 mid 거리만큼 떨어져 있는 다음 집을 찾는다.
        • 다음 집을 찾았을 경우 공유기를 설치 한다.
        • 두번째 집에서 mid 거리만큼 떨어져 있는 다음 집을 찾는다.(반복)
      • 반복 하여 주어진 공유기 갯수 만큼 설치 할 수 있는 mid 값을 찾는다.
        • mid 가 가장 큰값을 maxMid 변수에 담는다.

    • maxMid 값을 제출(출력)한다.

소스

  • 공유기 설치(2110)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Baekjoon_2110 {
	
	private static int c = 0; //공유기의 갯수
	private static int[] location;
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] inputA = reader.readLine().split(" ");
		
		//집의 갯수
		int n = Integer.parseInt(inputA[0]);
		//공유기의 갯수
		c = Integer.parseInt(inputA[1]);
		
		location = new int[n];
		
		for (int i = 0; i < n; i++) {
			location[i] = Integer.parseInt(reader.readLine());
		}
		Arrays.sort(location);
		System.out.println(Bsearch(1, location[location.length - 1]));
	}
	
	private static long maxMid = 0;
	public static long Bsearch(long left, long right) {
		long tmp = 0;
		int cnt = 0;

		long mid = (left + right) / 2;	//집간의 거리
		if(left > right) return maxMid;
		
		for (int i : location) {
			if( tmp == 0 ) { tmp = i; cnt++; continue; }
			
			if( i - tmp >= mid ) {
				cnt++;
				tmp = i;
			}
		}
		if(cnt >= c) {
			if(mid > maxMid) {
				maxMid = mid;
			}
			return Bsearch(mid + 1, right);
		}else {
			return Bsearch(left, mid - 1);
		}
	}
}

Back to blog