[Java] 백준 6209. 제자리 멀리뛰기

📌 문제 링크 - https://www.acmicpc.net/problem/6209

 

 

---

 

 

 

 

 

 

문제

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)를 포함하여 계산하여야 하기 때문에 주어지는 돌섬들의 거리를 저장하는 배열인 distance에 0과 D를 추가하여 정렬해 준다. 

 

- 이후 이분탐색을 통해 mid 값을 돌섬 사이의 최소 거리라고 가정하고, 돌섬들을 탐색하면서 이 최소 거리로 건너뛸 수 있는지 체크해 준다. 이때 돌섬 간의 거리가 mid 이상이어야 점프할 수 있고, mid 보다 작다면 돌섬을 제거한다. 제거한 돌섬의 개수가 M을 초과한다면 해당 최소 거리는 불가능한 것이다. 

 

- 최소 거리로 건너뛸 수 있다면 더 큰 점프 거리를 탐색하기 위해 start 값을 증가시켜주고, 불가능하다면 거리를 줄이기 위해 end 값을 감소시켜주며 탐색해 준다.

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/6209
public class Main_6209 {
    private static int D; // 탈출구까지의 거리
    private static int N; // 작은 돌섬의 수
    private static int M; // 제거할 수 있는 작은 돌섬의 수
    private static int[] distance; // 각 작은 돌섬 거리


    public static void main(String[] args) throws IOException {
        init();

        int result = getMax();
        System.out.print(result);
    }//main


    private static int getMax() {
        int max = 0;
        int start = 0;
        int end = D;
        int mid;

        while(start <= end) {
            mid = (start + end) / 2;

            if(isPossible(mid)) {
                start = mid + 1;
                max = mid;
            }
            else {
                end = mid - 1;
            }
        }

        return max;
    }//getMax


    private static boolean isPossible(int min) {
        int cnt = 0;
        int prev = 0;
        int end = N + 1;

        for(int i=1; i<=end; i++) {
            if(distance[i] - prev < min) {
                if(++cnt > M) return false;
            }
            else {
                prev = distance[i];
            }
        }

        return true;
    }//isPossible


    private static void init() 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()); // 제거할 수 있는 작은 돌섬의 수

        distance = new int[N+2];
        distance[N+1] = D;

        for(int i=1; i<=N; i++) {
            distance[i] = Integer.parseInt(br.readLine());
        }

        br.close();
        Arrays.sort(distance);
    }//init


}//class

 

 

 

시간복잡도

O(NlogN)