문제
GSHS에서는 체력측정에서 제자리 멀리뛰기가 가장 중요하다. GSHS의 체육선생님께서는 학생들의 제자리 멀리뛰기 실력을 키워주게 하기 위해서 특수 훈련을 준비중이다.
특수 훈련장소는 GSHS특수 트레이닝 센터로 이 곳은 끓는 용암으로 가득 차 있다. 체육선생님께서는 이 용암으로 가득찬 방의 가운데 있는 돌섬에 학생들을 가두고 학생들이 탈출해 나오기를 기대하고 있다. 탈출할 수 있는 방법은 단 한가지 이다. 돌섬에서 탈출구까지 띄엄 띄엄 존재하는 작은 돌섬들로 점프하여 탈출구까지 가는 것이다.
돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬이 있다. 선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다. 물론 학생들은 체력이 좋기 때문에 두 돌섬이 아무리 멀더라도 점프할 수 있다. 즉, 빠지는 일은 없다.
그리고 학생들은 탈출 시 n-m개의 모든 돌섬을 밟으면서 탈출해야 한다.
학 생들이 갇힌 돌섬으로부터 탈출구까지의 거리 d가 주어지고, 각 n개의 작은 돌섬의 위치(갇힌 돌섬으로 부터의 거리)가 주어지며, 제거할 수 있는 작은 돌섬의 수 m이 주어질 때, m개를 제거한 후 학생들이 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 <= d <= 1,000,000,000), 작은 돌섬의 수 n(0 <= n <= 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 <= m <= n)이 공백으로 구분되어 주어진다.
두 번째 줄부터 n줄에 걸쳐서 갇힌섬으로부터 각 작은 돌섬이 얼마나 떨어져 있는지를 나타내는 하나의 정수가 한 줄에 하나씩 주어진다. (단, 두 돌섬은 같은 위치에 있을 수 없다.)
출력
m개의 작은섬을 제거한 뒤 학생들이 점프할 수 있는 최소거리의 최댓값을 출력한다.
풀이
전형적인 매개 변수 탐색 문제다. "최소 점프 거리를 mid 이상으로 만들 수 있는가?"를 판정하면 된다.
돌을 왼쪽부터 보면서 직전으로 남겨 둔 돌과의 거리가 mid보다 작으면 그 돌은 제거해야 하고, mid 이상이면 남긴다. 이렇게 해서 제거한 돌의 개수가 m 이하면 mid는 가능한 값이다.
가능하면 더 큰 최소 거리를 탐색하고, 불가능하면 줄이는 이분 탐색으로 답을 찾는다.
판정이 그리디로 되는 이유는, 최소 점프 거리를 mid 이상으로 유지하려면 현재 돌을 남길 수 있을 때 굳이 제거할 이유가 없기 때문이다. 반대로 거리가 mid보다 작다면 둘 중 하나는 반드시 없어져야 하므로, 현재 돌을 제거하는 선택이 자연스럽다.
코드에서는 마지막 도착점 d를 배열에 넣지 않고도 같은 논리로 이분 탐색을 진행한다. 남겨진 돌들 사이의 최소 간격을 최대화하는 문제를 "이 간격이 가능한가?"라는 판정 문제로 바꾸는 것이 핵심이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int d, n, m;
static int[] rocks;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
d = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
rocks = new int[n + 1];
for (int i = 1; i <= n; i++)
rocks[i] = Integer.parseInt(br.readLine());
Arrays.sort(rocks);
System.out.println(solve());
}
static int solve() {
int ans = 0;
int left = 0;
int right = d;
while (left <= right) {
int mid = (left + right) / 2;
int idx = 0;
int cnt = 0;
// 최소거리 찾기
for (int i = 1; i <= n; i++) {
// 돌섬 제거하면서 계산
if (mid <= rocks[i] - rocks[idx])
idx = i;
else
cnt++;
}
// cnt가 m을 넘어서면 최소거리가 아님
if (cnt > m)
right = mid - 1;
else {
ans = mid;
left = mid + 1;
}
}
return ans;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
어떤 최소 점프 거리가 가능한지만 판정해 보면 구조가 단순해진다. 돌 제거 문제는 이런 식의 이분 탐색으로 자주 바뀐다.
