[BOJ] 2110 공유기 설치_JAVA

 

[ 문제 ]

www.acmicpc.net/problem/2110

2110번: 공유기 설치

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

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

[ 입력 ]
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

[ 출력 ]
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

 

 

 

---

 

[Solution 1]
- 결과는 맞지만 시간초과
- 입력조건이 ‘2 ≤ N ≤ 200,000’ ‘0 ≤ xi ≤ 1,000,000,000’인데 당연쓰...
- 이렇게 말도안되는 max값이 주어진다면 이진탐색으로 접근해보기

package boj2110_공유기설치;

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

public class Main {
	static int c, n;
	static int[] combi;
	static int [] hp;
	static PriorityQueue<Integer> minArr = new PriorityQueue<Integer>(Collections.reverseOrder());
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());	//도현이집 개수
		c = Integer.parseInt(st.nextToken());	//공유기 개수
		
		hp = new int[n];
		combi = new int[c];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			hp[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(hp);
		combination(0, 0);
		
		System.out.println("RESULT : " + minArr.poll());
	}
	
	static void combination(int r, int start) {
		if(r == c) {
			int min = hp[n-1];
			for(int i=0; i<c-1; i++) {
				if(i+1 < c) {
					min = Math.min(min, combi[i+1] - combi[i]);
				}
			}
			minArr.add(min);
			
			return;
		}
		
		for(int i=start; i<n; i++) {
			combi[r] = hp[i];
			combination(r+1, i+1);
		}
	}
}

 

 

[Solution 2]
- 이진탐색

package boj2110_공유기설치;

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

public class Main2 {
	static int c, n;
	static int [] hp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());	//도현이집 개수
		c = Integer.parseInt(st.nextToken());	//공유기 개수
		
		hp = new int[n];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			hp[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(hp);
		
		int min = 1;				//공유기간 최소거리
		int max = hp[n-1] - 1;		//공유기 간 최대거리
		int answer = 0;
		
		while(min <= max) {
			int middle = (max+min)/2;		//공유기 거리 기준
			int prev = hp[0];				//첫 위치 설치
			int cnt = 1;					//설치한 공유기 수
			
			for(int i=0; i<n; i++) {
				int distance = hp[i] - prev;	//거리차
				
				if(distance >= middle) {		//거리차가 기준보다 크거나 같아야 설치 가능
					cnt++;
					prev = hp[i];
				}
			}
			
			//공유기 설치가 c보다 더 많으면 간격을 넓혀서 개수를 줄임
			if(cnt >= c) {
				min = middle + 1;
				answer = middle;
			} else {
				max = middle - 1;
			}
		}
		System.out.println(answer);
	}
}