문제 링크

성능 요약

메모리: 28960 KB, 시간: 260 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2025년 2월 13일 00:59:03

문제 설명

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

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

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

입력

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

출력

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

풀이

느낀점

• 최근에 이분탐색 문제를 몇개 풀어서 그런지 비교적 풀만 했다.
• 그런데 생각보다 엄청 빠른 느낌은 아니다.

설계 : 20분

• 무작위로 입력되는 집의 좌표를 모두 int[] house 배열에 저장한 후 오름차순으로 정렬한다.
• 첫번째 집과 마지막 집의 거리를 (설치할 공유기 수 - 1) 으로 나눈 수가 답이 될 수 있는 가장 먼 거리(max)이다.
• low = 1, high = max 로 설정한 후 이분탐색을 실시한다.
  • 모든 집을 순서대로 순회하며 거리가 mid 이상인 집을 만날때마다 공유기를 설치한다.
  • 순회를 끝낸 후 남은 공유기 수가 0이면 가능한 경우이고, 아니라면 불가능한 경우이다.
  • 가능한 경우이면 답을 갱신한 후 low = mid +1 해서 더 긴 거리를 테스트하고, 불가능한 경우라면 high = mid - 1 해서 더 짧은 거리를 테스트한다.

코드(Java)

• 구현 시간: 15분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 공유기 설치_2110
 * Date: 2025.02.13
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[] house;
	static int n;
	static int c;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		n = Integer.parseInt(input[0]);
		c = Integer.parseInt(input[1]);

		house = new int[n];
		for (int i = 0; i < n; i++) house[i] = Integer.parseInt(br.readLine());
		Arrays.sort(house);

		int low = 1;
		int high = (house[n-1] - house[0]) / (c-1);

		int mid;
		int answer = 0;
		while (low <= high) {
			mid = (low + high) / 2;

			if (isPossible(mid)) {
				answer = mid;
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

	public static boolean isPossible(int dist) {
		int cnt = c;
		int idx = 0;
		while (cnt > 0 && idx < n) {
			int a = house[idx];
			while (idx < n && house[idx] - a < dist) idx++;
			cnt--;
		}
        return cnt <= 0;
    }
}