[백준 - 1508] 레이스 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 이분탐색

입력

첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같은 자연수이다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어진다. K개의 위치는 N보다 작거나 같은 자연수 또는 0이며, 오름차순으로 주어진다.

출력

첫째 줄에 심판을 어떻게 배치시켜야 가장 가까운 심판의 거리가 최대가 될 것이지 출력한다. 출력할 때는 예제와 같이 심판을 세울 곳에는 1을, 세우지 않을 곳에는 0을 출력한다. 만약 정답이 여러개일 경우에는 사전순으로 가장 늦는 것을 출력한다.

풀이

심판 간의 거리가 커질수록, 배치할 수 있는 자리가 적어지고, 작아질수록 배치할 수 있는 자리가 많아진다.

이는 전형적인 이분탐색의 조건이다.

N이 최대 1,000,000이기 때문에 거리는 1 ~ 1,000,000 이 범위라고 할 수 있다.

그러면 일단, 심판 간의 거리는 특정할 수 있는데, 그 거리가 가능한지, 가능하지 않은지 어떻게 체크해야 할까?

배치될 수 있는 K개의 위치는 오름차순으로 주어진다. 첫 번째로 심판을 배치할 자리는 가장 왼쪽이 최선의 선택이 된다. 왜냐하면 가장 왼쪽이 가장 작은 수이며, 그 다음 배치 자리와의 차이를 가장 크게할 수 있기 때문이다.

예를 들어 0 5 10 11이면, 0이 5, 10, 11과의 차이가 가장 크지, 5가 10, 11과의 차이가 가장 크지는 않다.

배치할 첫 번째 자리가 정해졌다면, 다음 배치 자리도 가장 왼쪽에 있으면서, 조건에 부합하는(특정한 심판 간의 거리보다 크거나 같은) 자리가 최선의 선택이 된다.

그러니까 우리는 배치할 각 자리를 최선의 선택으로 정할 수 있고, M명을 배치했다면 가능하고, 그렇지 않다면 가능하지 않다고 판단할 수 있는 것이다.

그래서 이분탐색 + 그리디 풀이의 시간 복잡도는 O(K * log N)이 된다.

소스 코드

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

public class Main {
    static int N, M, K;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int[] line = new int[K];

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

        System.out.println(binarySearch(line));
    }

    static String binarySearch(int[] line) {
        String answer = "";
        int min = 1;
        int max = N;

        while (min <= max) {
            int mid = (min + max) / 2;
            String result = posible(line, mid);
            
            if(result == "") {
                max = mid - 1;
            } else {
                min = mid + 1;
                answer = result;
            }
        }

        return answer;
    }

    static String posible(int[] line, int std) {
        int cout = 0;
        StringBuilder sb = new StringBuilder();
        sb.append(1);
        cout += 1;
        int before = line[0];
        for (int i = 1; i < line.length; i++) {
            if (cout == M) {
                //배치가 다 되었다면
                sb.append(0);
            } else {
                if (line[i] - before >= std) {
                    //기준에 부합한다면
                    sb.append(1);
                    cout += 1;
                    before = line[i];
                } else {
                    sb.append(0);
                }
            }
        }
        if (cout == M) {
            return sb.toString();
        }
        return "";
    }
}