백준 1508번 : 레이스 [자바]

 

🧫 문제 분석

 

✔️ 출처

레이스 골드 2

 

📖 문제

 

이분탐색 + 그리디문제

 

이분탐색의 대상은 두 심판의 거리다.

M명 배치할 수 있는 심판의 거리를 구해서 

심판을 배치하고 그 중에서 가장 가까운 거리가 가장 긴 심판 배치를 출력한다.

 

그런데 가장 긴 심판 배치는 

심판 거리계산하면서 자동으로 마지막에 계산된 것이 가장 긴 거리가 된다. 

(더 긴 거리를 탐색해보기 때문)

 

비슷한 문제로 예전에 풀었던 공유기 설치 문제랑 비슷하다.

 

나의 경우

심판 배치 거리 탐색 - 이분탐색

적절한 심판 배치 위치 탐색 - 이분탐색

 

3중 while문으로 풀어서 좀 보기 안좋을 수 있다.

심판 위치 배치는 for문으로 해도 된다. 

 

 

---

🔅 문제 풀이

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

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 M = Integer.parseInt(st.nextToken()) - 1; // 처음 무조건 선택
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[K];
        char[] answer = new char[K];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 두 심판과의 거리 탐색
        int start = 0, end = arr[K-1] - arr[0];
        while (start <= end) {

            int dist = (start + end) >>> 1;

            // 심판 배치 배열
            char[] tmp = new char[K];
            Arrays.fill(tmp, '0');
            tmp[0] = '1'; // 처음 위치 선점

            // 거리 계산 기준 인덱스
            int idx = 0, cnt = 0;
            while (cnt < M) {

                // 적절한 심판 배치 위치 탐색
                int left = idx, right = K - 1;
                while (left < right) {

                    int mid = (left + right) >>> 1;

                    if (arr[mid] - arr[idx] < dist) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }

                // 더이상 탐색 불가로 탐색 중지
                if (arr[left] - arr[idx] < dist) {
                    break;

                } else {
                    tmp[left] = '1';
                    idx = left;
                    cnt++;
                }
            }

            // cnt가 M 이상이면 더 긴 길이로 탐색
            if (cnt >= M) {
                start = dist + 1;
                answer = tmp;
            } else {
                end = dist - 1;
            }
        }

        System.out.println(answer);

    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  어떤 정점 여러개를 배치하는데 어떤 정점과의 거리가 최대 혹은 최소가 되는 것을 구해야하는 문제의 경우 거리 이분탐색을 떠올려보자