[백준] 2110번:공유기 설치 (Java 자바)

문제

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

2110번: 공유기 설치

 

풀이 및 소스코드

 

ㅋㅋㅋ문제 이해가 안됐던 문제다..

 

설명해보면

현재 집의 좌표가 arr = (1, 2, 4, 8, 9) 라고 하자 ! (백준 예제임)

start = 1

end = arr[n-1]-arr[0] // 공유기를 놓을 수 있는 최대 거리

으로 초기화를 할 수 있다.

 

즉, 1에 놓고 9에 놓으면 최대거리 8 !! 이렇게 양 끝을 잡고 이분탐색을 통해 c(3)개의 공유기가 놓이면서, 공유기 사이의 최대거리를 구하면 된다.

 

이어서 설명하자면 mid는 (9-1)/2 인 4가 된다.

 

1. 최대 거리 : 4

첫번째 집에 공유기를 설치한다.

현재 공유기 위치 : home[0]

다음 공유기를 설치 할 수 있는 최소 거리 : now = home[0]+mid

집들의 좌표를 처음부터 비교해서 다음 공유기를 설치할 수 있는지 확인한다.

arr = (1, 2, 4, 8, 9)  now보다 작음. 설치불가 !

arr = (1, 2, 4, 8, 9)  now보다 작음. 설치불가 !

arr = (1, 2, 4, 8, 9)  now보다 큼. 설치 가능.

=> now = home[3]+mid

arr = (1, 2, 4, 8, 9)  now보다 작음. 설치 불가 !

cnt 는 총 2개로, c보다 작으므로 간격을 줄여서 공유기를 설치해야한다.

 

간격을 줄여야하므로, end = mid-1 로 바꾼다.

2. 최대 거리 : 3

arr = (1, 2, 4, 8, 9)  now보다 작음. 설치불가 !

arr = (1, 2, 4, 8, 9)  now보다 큼. 설치 가능.

=> now = home[2]+mid

arr = (1, 2, 4, 8, 9)  now보다 큼. 설치 가능.

=> now = home[3]+mid

arr = (1, 2, 4, 8, 9)  now보다 작음. 설치 불가 !

 

3개 설치가 되는 거리 3을 찾아냈다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int[] home = new int[n];
		for(int i=0;i<n;i++) {
			home[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(home); //오름차순 정렬
		
		int start = 1; //시작점
		int end = home[n-1]-home[0]; //공유기의 최대거리
		int res = 0;
		while(start<=end) {
			int cnt = 1;
			int mid = (start+end)/2;
			int now = home[0]+mid; //첫번째 공유기 설치+거리
			for(int i=0;i<n;i++) {
				if(now<=home[i]) { //만약에 인접한 공유기와 mid 이상의 차이가 나면
					now = home[i]+mid;
					cnt ++; //공유기 설치 !
				}
			}
			boolean flg = cnt>=c? true: false;
			if(flg) {//c이상 설치가 가능할 때 mid값 들 중 최댓값을 구하자!
				res = Math.max(res, mid);
				//최댓값을 찾는 것이므로
				start = mid+1;
			}else {//공유기 너무 적게 설치 ㅠ 간격을 줄이자.
				end = mid-1;
			}
		}
		System.out.println(res);
	}
	
}