[BOJ2110/Java] 공유기 설치

1. 문제 요약

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

2110번: 공유기 설치

N개의 집 중에서 공유기를 설치할 C개의 집을 찾는다고 이해하면 제일 편한데

근데 이렇게 생각하면 조합이 떠오른다. 그치만 200,000개의 집 중에서 100,000개의 공유기를 설치할 집을 고른다?

말이 안된다.. 다른 방법을 찾아야 함

 

2. 입/출력

앞에서도 말했듯 조합으로 생각하기에는 숫자가 너무 크다.. 그렇다면 어떻게 해야할까?

 

3. 접근 아이디어

다행이도 전에 이와 비슷한 문제를 풀어본 적이 있다.

(참고: 제자리 멀리뛰기 https://www.acmicpc.net/problem/6209)

우리는 선택할 집을 고르는 것이 아니라 A에서 B까지 일정 거리 이상이 되면 공유기를 놓는다고 생각한다.

그럼 집을 보는 것 대신 집과 집 사이의 거리를 보게 되고, 집과 집 사이 거리가 내가 정한 기준을 넘어서면 공유기를 놓는식으로 한다.

그렇다면 공유기를 놓는 기준 거리는 어떻게 찾을 수 있을까? => 여기서 이분 탐색을 이용할 것임. 정확히는 파라미터 탐색.

1) 일단 0과 제일 먼 거리 사이에서 기준거리(mid)를 찾는다.

2) h1을 첫 공유기 설치자리로 선택하고 h2, h3 다음 집을 살펴보는데 h1과 hi 사이의 거리가 mid보다 멀다면 hi 집에 공유기를 설치하고(cnt++) hi의 위치를 공유기 설치자리(now)로 설정한다.

3) 이후 탐색을 계속하게 되면 기준거리에 대하여 공유기를 몇개나 설치할 수 있는지 알 수 있다.

4) 설치할 수 있는 공유기의 개수가 설치해야하는 공유기 개수보다 작다면

   => 기준 거리를 낮춰야 함. r = mid -1로 재설정

5) 설치할 수 있는 공유기의 개수가 설치해야하는 공유기 개수보다 같거나 크다면

   => 더 높은 기준거리에서도 이를 만족할 수 있는 지 확인하기 위해서 기준거리를 높여야 함. l = mid+1로 재설정

이후 2~5를 반복하면 최대 거리를 찾을 수 있음!

 

4. 작성코드

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

public class Main {

	public static void main(String[] args) throws Exception{
		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());
		
		int[] house = new int[N];
		for(int i = 0; i<N; i++) {
			house[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(house);
//		System.out.println(Arrays.toString(house));
		int l = 0, r = house[N-1], ans = 0;
		
		while(l<=r) {
			int mid = (l+r)/2;
//			System.out.println(mid);
			int cnt = 0;
			int now = house[0];
			int min = house[N-1];
			for(int i : house) {
				if((i-now) >= mid) {
					min = Math.min(min, i-now);
//					System.out.println(now+" "+i+" "+min);
					now = i;
					cnt++;
				}
//				else {
//					System.out.print(i+" ");
//				}
			}
//			System.out.println(cnt+"\n");
			
			if (cnt < C-1){
				r = mid - 1;
			}
			else {
				ans = Math.max(ans, min);
				l = mid + 1;
//				System.out.println("new ans"+ans);
			}
			
		}
		
		System.out.println(ans);
	}

}