문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 이분 탐색, 매개 변수 탐색
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개의 작은섬을 제거한 뒤 학생들이 점프할 수 있는 최소거리의 최댓값을 출력한다.
풀이
처음에 나는 점프하는 최소 거리를 최댓값으로 만들기 위해서 뛰는 거리가 최소인 값을 순차적으로 제거해 주는 방식을 생각했다. 이 방식은 돌섬을 제거할 때마다 업데이트해야 하기 때문에 시간 초과가 발생한다.
다른 방식을 생각하면서, 이분 탐색을 적용할 수 있는 특징?을 찾을 수 있었다.
학생이 뛰는 거리를 정했을 때 이 거리가 클수록 밟을 수 있는 돌섬이 적어지고, 반대로 작아지면 밟을 수 있는 돌섬이 많아진다. 전형적인 이분 탐색 문제다.
이분 탐색 풀이를 자세하게 설명하자면,
최솟값은 0이고, 최댓값은 d다. 뛰는 거리는 d를 넘지 못한다.
뛰는 거리는 mid = (min + max) / 2; 값으로
mid를 이용해서 순차 탐색을 해준다. 이때 돌섬은 오름차순으로 정렬되어 있어야 하고, 마지막 탈출구인 d도 포함되어 있어야 한다.
순차 탐색을 하면서
전에 위치한 prev + mid <= rocks[i] 인 경우 해당 돌섬을 밟을 수 있다는 의미다. 그렇기 때문에 cnt += 1를 해준다.
탐색을 마치고 cnt를 이용해 min, max를 업데이트 해준다.
cnt >= n - m + 1 라면 m개보다 같거나 더 적은 수의 돌섬을 제거해도 가능하다는 의미이다.
그래서 min = mid + 1 해준다.
else인 경우는 m개보다 더 많은 수의 돌섬을 제거해야 하기 때문에 불가능하다.
그래서 max = mid - 1 해준다.
이를 반복해주면 max 값이 점프할 수 있는 최소거리의 최댓값이 된다.
시간복잡도는 O(n * logd)로 충분히 가능하다.
소스 코드
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];
rocks[n] = d;
for(int i=0; i<n; i++) {
rocks[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(rocks);
System.out.println(binarySearch());
}
static int binarySearch() {
int min = 0;
int max = d;
while(min <= max) {
int mid = (min + max) / 2;
if(check(mid)) {
//true면 가능
min = mid + 1;
} else {
max = mid - 1;
}
}
return max;
}
static boolean check(int jd) {
int cnt = 0;
int prev = 0; //전에 위치한 돌
for(int i=0; i<rocks.length; i++) {
if(prev + jd <= rocks[i]) {
cnt += 1;
prev = rocks[i];
}
}
if(cnt >= n - m + 1) {
return true;
}
return false;
}
}