백준_공유기 설치_2110

//알고리즘

1. 이분 탐색문제

 

2.  N값이 최대 20만이기 때문에 아이디어가 필요함

 -> 최대의 거리를 변경해가면서 찾아야 함. 

 

3. 시작점은 가장왼쪽집 끝점은 가장오른쪽집으로 시작해서 중간값(최대 거리)을 구함

 

4. 최대거리를 넘는 집의 개수를 구해서 설치해야할 공유기의 수보다 크거나같다면 시작점을 1씩 더해주고

   작다면 끝점을 1씩 빼서 결과값을 찾아 냄 (이분 탐색)

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

public class 공유기설치_2110 {

	static int N, C;

	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());

		int[] arr = new int[N];
		int ans = 0;

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);

		int left = 1;
		int right = arr[N - 1] - arr[0];
		int dist = 0;

		// 알고리즘
		while (left <= right) {
			int mid = (left + right) / 2;
			int start = arr[0];
			int cnt = 1;

			for (int i = 1; i < N; i++) {
				dist = arr[i] - start;
				if (mid <= dist) {
					++cnt;
					start = arr[i];
				}
			}

			if (cnt >= C) {
				ans = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}

		System.out.println(ans);

	}
}

 

 

※ 이 문제에서 이분 탐색을 떠올리기가 쉽지 않았음. 강의에서 들었던 이분 탐색 코드를 실제 알고리즘에 처음 적용해봤고 자주 구현하지 않아서 어려웠음. 다른 분 블로그에서 풀이법을 보고 작성한 코드라 다음에 시간 내서 풀어봐야 할 거 같다...