자바 백준 2110번 문제 : 공유기 설치

문제 출처 : https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

문제 :

 

풀이 :

Parametric Search 알고리즘 통해 간단하게 문제를 해결할 수 있다.

우선 Arrays.sort(arr) 하면 1 2 4 8 9

lt = 1 , rt = 9(arr에서 최대값) , mid = 5

mid = 5로 잡은 것은 가장 가까운 두 공유기 최대 거리가 5라고 가정하고 넣어보는 것이다.

따라서 count 함수를 만들어 5가 가장 가까운 두 공유기의 거리인지 갯수를 세서 확인하면 된다.

거리가 5 이상인 공유기 개수를 세면 된다.

공유기들을 배치할 때 방금 배치한 공유기 x좌표를 저장할 ep 변수, 개수를 cnt로 둔다.

cnt가 C의 값보다 크거나 같을 경우 구하고자 하는 값이 현재 mid값보다 크다는 것이므로 lt = mid + 1 한다.

cnt가 C의 값보다 작을 경우 구하고자 하는 값이 현재 mid값보다 작다는 것이므로 rt = mid - 1 한다.

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	public int count(int[] arr, int mid) {
		int cnt = 1, ep = arr[0];
		for(int i=1; i<arr.length; i++) {
			if (arr[i] - ep >= mid) {
				cnt++;
				ep = arr[i];
			}
		}
		return cnt;
	}
	public int solution(int n, int c, int[] arr) {
		int answer = 0;
		Arrays.sort(arr);
		int lt = 1, rt = arr[n-1];
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (count(arr, mid) >= c) {
				answer = mid;
				lt = mid + 1;
			}
			else rt = mid - 1;
		}
		return answer;
	}
	public static void main(String[] args) throws IOException {
		Main T = new Main();
		//Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		bw.write(String.valueOf(T.solution(n, c, arr)));
		bw.flush();
		bw.close();
	}
}

 

실행결과 :