[백준2110번] 공유기설치

2110번: 공유기 설치

문제 이해

하나의 좌표 위에 여러개의 집이 존재하는 경우는 없다

• 집에는 공유기 C 개를 설치하려고 한다.
• 최대한 많은 곳에서 와이파이를 사용하고 싶다.
  • 따라서, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
• 한 집에는 공유기를 하나만 설치할 수 있다.

C개의 공유기를 N개의 집에 적당히 설치해, 가장 인접한 두 공유기 사이 거리를 최대로 하는 프로그램을 작성하자

• 공유기의 개수 (C) ≤ 집의 개수 ( N )

문제 풀이

가장 인접한 두 공유기 사이의 거리가 최대가 되도록 하는 “거리" 를 구해야 한다.

• 가장 인접한 두 공유기 사이의 최대 거리를 d 로 해서

  • d 로, 공유기 C 개를 설치하는 것이 가능한지 알아볼 수 있을까?

    즉, 모든 두 공유기 사이의 거리가 d 이상일 수 있는지를 판단.

  1. 집을 오름차순으로 정렬한다.
  2. 현재 집에서 거리 d 이상 떨어진 바로 다음 집에 공유기를 설치
  3. 이를 반복하며 공유기 C 개를 설치하는게 가능하다면 → 최대 거리를 늘려 볼 수 있다.

• 이렇게 할 경우, d 를 결정하는 방식이 문제가 될 것이다.

  • 이진 탐색을 사용할 경우 최종 정답 까지 O(log(최대xi))

• 각 d 에 대해 최대 O(n) 의 탐색이 필요

• 어떤 거리에서 가능한 경우 → left 를 늘려야 한다. + 현재 Mid 를 저장하고 있어야 한다.

  • 불가능한 경우 right 를 줄여야 한다.

package acmicpc;

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

public class Main {
	public static int n; // 집의 개수
	public static int c; // 공유기의 개수
	public static int loc[]; // 집의 좌표 위치를 나타내는 테이블

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;

	public static void setUp() throws IOException {

		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		loc = new int[n];

		for(int i=0;i<n;i++){
			loc[i] = Integer.parseInt(br.readLine());
		}

		// 집의 위치들을 오름차순으로 정렬
		Arrays.sort(loc);

	}
	
	public static int bin_search(){
		int left = 0, right = loc[n-1]-1;
		int mid = 0, ans = -1;
		while(left <= right){
			mid = (left + right) / 2;

			if(isPossible(mid)){
				left = mid+1;
				ans = mid;
			}else{
				right = mid -1;
			}
		}

		return ans;
	}

	// 거리 d 로 가능 한 건지
	// 차례 차례 채워 나가보면 된다
	public static boolean isPossible(int d){
		boolean ans = true;
		int cnt = 1;
		int pre = loc[0]; // 공유기를 설치한 이전 집

		for(int i =1; i < n;i++){
			// 현재 집에 공유기 설치 가능한 경우 
			if(loc[i]-pre >= d){
				pre  = loc[i];
				cnt++;
			}
		}
		if(cnt < c) ans = false;

		return ans;
	}

	public static void main(String[] args) throws IOException {
		setUp();
		System.out.println(bin_search());
	}
}