(Java) Baekjoon 공유기설치 - 매개변수 탐색

2110번: 공유기 설치 (acmicpc.net)

 

 

소프티어랑 거의 똑같은 문제

package baekjoonGold;

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

public class Main2110_공유기설치_1 {

	static int N, C, arr[], max;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] st = br.readLine().split(" ");
		N = Integer.parseInt(st[0]);
		C = Integer.parseInt(st[1]);
		arr = new int[N];

		for (int i = 0; i < N; i++)
			arr[i] = Integer.valueOf(br.readLine());

		Arrays.sort(arr);

		int left = 1;
		int right = arr[N - 1] - arr[0];	//최대 간격
		int result = 0;

		while (left <= right) {
			int cnt = 1;
			int cur = arr[0];				//첫번째 집부터 시작
			int mid = (left + right) / 2;

			for (int i = 1; i < N; i++) {	//두번째 집부터 시작
				if (arr[i] - cur >= mid) {
					cnt++;
					cur = arr[i];			//현재 커서를 설치한 집으로 이동
				}
			}

			if (cnt >= C) {					//최소 C개만큼 설치했을 경우
				result = mid;
				left = mid + 1;				//간격 넓히기
			} else
				right = mid - 1;			//간격 좁히기
		}
		System.out.println(result);
	}
}

 

여전히 아직 이해가 잘 안되는 것 같아요 ,, 다시 읽어볼 것