백준 2210번: 공유기 설치
가장 인접한 두 공유기 사이의 최대 거리를 출력해야 하는 문제다. 즉, 최소 거리가 최대가 될 때의 거리를 구해야 한다.
(가장 약한 놈이 그나마 제일 강할 때를 구하라)
잘못된 첫 접근법
n개의 집에 c개의 공유기를 설치할 때, 가장 인접한 두 공유기 사이의 거리는 공유기 배치를 어떻게 하냐에 따라 달라진다. 그러므로 공유기 배치를 어떻게 할까에 집중했다.
그런데, 도저히 내 머리로는 일정한 규칙을 찾을 수가 없었다.
그나마 내가 생각해낸 아이디어는, 첫 번째 집과 마지막 집에는 공유기를 설치한 상태로 시작하자 정도였다.
하지만, 중간중간에 어떤 집에 공유기를 설치할지에 대해서는 생각해내지 못 하고 결국 풀이법을 찾아봤다.
올바른 접근법
이 문제는 결국, 구해야 하는 최소거리에 집중해야 한다.
우리가 설정한 최소거리 t에 따라 설치할 수 있는 공유기 수가 정해지게 되는데, 우리는 t가 최소 거리중 최대일 때를 찾아내는 것이다.
이렇게 t의 값을 바꿔가며 답을 찾아내는 것이고, t를 바꿔가는 과정에서 이분 탐색을 사용할 것이다.
결국 핵심은 다음과 같다.
- 입력받은 좌표를 오름차순 정렬하고, 첫 번째 집에 공유기를 설치한 상태에서 시작한다.
- 최소거리
t를 설정한다. i번째 공유기를 설치한 집으로부터t이상의 거리를 두고 있는 집 중, 가장 가까운 집에i+1번째 공유기 설치한다.- 마지막 집까지 2번 과정을 반복한 뒤에 설치된 공유기 수를 확인한다.
이때, 설치된 공유기 수와 가지고 있는 공유기 수를 비교한다.
(가지고 있는 공유기 수는 문제에서 입력값 c로 주어진다.)
- 설치된 수 > 가지고 있는 수 : 최소거리를 작게 설정했기 때문에 가지고 있는 공유기의 수보다 많은 양을 설치하게 된다. -> 최소거리를 늘린다.
- 설치된 수 < 가지고 있는 수 : 최소거리를 크게 설정했기 때문에 가지고 있는 공유기를 다 못 쓰게 된다. -> 최소거리를 줄인다.
- 설치된 수 == 가지고 있는 수 : 우리가 결국 구해야 하는 상황인
최소 거리가 최대일 때인지 알 수 없기 때문에 -> 최소거리를 늘린다.
이분 탐색 + 매개 변수 탐색의 과정이다.
중요한 점은, 설치된 수가 c와 같아져도 최대인지 알 수 없기 때문에 최소 거리를 늘리면서 최대일 때를 찾는다는 것이다.
결국, 조건을 부합(설치된 수 == 가지고 있는 수)하지 않기 직전 값을 구하면 된다.
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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());
}
Arrays.sort(arr);
int lo = 1; // 가능한 최소 간격
int hi = arr[n - 1]; // 입력받은 집들의 최대 간격
while (lo <= hi) {
int mid = (lo + hi) / 2; // 최소 거리 설정
int position = 0; // 공유기 설치 위치(처음부터 시작)
int cnt = 1; // 설치 가능한 공유기 수
for (int i = 1; i < n; i++) {
if (arr[i] - arr[position] >= mid) {
position = i;
cnt++;
}
}
if (cnt < c) { // 설치된 공유기 수가 가지고 있는 공유기의 수보다 적으면
hi = mid - 1; // upper bound 내림으로써 최소 거리 줄인다.
continue;
}
//설치된 공유기 수가 가지고 있는 공유기 수보다 크다면
lo = mid + 1; // lower bound 올림으로써 최소 거리 늘린다.
}
// 설치한 수 == 가지고 있는 수가 되었을 때 while문을 끝내지 않고
// 설치한 수 < 가지고 있는 수가 될 때가 되었을 때 끝냈기 때문에
// 최소 거리의 최대(조건을 부합하지 않기 직전) 값을 출력하기 위해 1을 빼준다.
System.out.println(lo - 1);
}
}
개발 기록