[BaekJoon] 1508 레이스 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1508

2.  문제

3.  소스코드

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

public class Main {
    static int length;
    static int refereeCount;
    static int pointCount;
    static int[] points;
    static int[] status;

    static void input() {
        Reader scanner = new Reader();

        length = scanner.nextInt();
        refereeCount = scanner.nextInt();
        pointCount = scanner.nextInt();
        points = new int[pointCount];

        for (int idx = 0; idx < pointCount; idx++) {
            points[idx] = scanner.nextInt();
        }
    }

    /*
     * 가장 가까운 두 심판의 거리를 이분 탐색을 통해 구할 매개 변수로 정하고
     * 이분 탐색을 통해 가장 가까운 두 심판의 거리의 최댓값을 구한다
     * 각 탐색마다 가장 가까운 거리가 정해지는데, 해당 거리가 가장 가까운 거리일 때 세울 수 있는 심판의 수를 구한다
     * 심판이 M명 세워질 때의 거리 중 최댓값을 구하고, 사전순 가장 늦는 것을 출력해야하므로 1번부터 세워보며 세울 M명을 구한다
     */
    static void solution() {
        int minDistance = binarySearch();
        findAssignedRefereeCount(minDistance, true);
        printAnswer();
    }

    static void printAnswer() {
        StringBuilder answer = new StringBuilder();
        int count = 0;
        for (int idx = 0; idx < pointCount; idx++) {
            if (count >= refereeCount) {
                answer.append(0);
                continue;
            }

            answer.append(status[idx]);
            if (status[idx] == 1) {
                count++;
            }
        }
        System.out.println(answer);
    }

    static int binarySearch() {
        int left = 0;
        int right = length;

        while (left <= right) {
            int mid = (left + right) / 2;
            int assignedRefereeCount = findAssignedRefereeCount(mid, false);

            if (assignedRefereeCount >= refereeCount) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return right;
    }

    static int findAssignedRefereeCount(int minDistance, boolean isFindingAnswerProceed) {
        int answer = 0;

        for (int basisIdx = 0; basisIdx < pointCount; basisIdx++) {
            status = new int[pointCount];
            status[basisIdx] = 1;
            int count = 1;
            int curPoint = points[basisIdx];
            for (int otherIdx = basisIdx + 1; otherIdx < pointCount; otherIdx++) {
                if (points[otherIdx] - curPoint >= minDistance) {
                    status[otherIdx] = 1;
                    curPoint = points[otherIdx];
                    count++;
                }
            }

            if (isFindingAnswerProceed && count >= refereeCount) {
                return count;
            }
            answer = Math.max(answer, count);
        }

        return answer;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}