[BOJ] 백준 1508 : 레이스 (java)

🧪 1508 레이스

---

난이도 : 🌟 골드 2
유형 : 이분탐색

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

 

📝 문제

---

세준이는 세준항공으로 돈을 무지막지하게 번 뒤, 레이스 대회를 개최했다. 레이스 트랙은 길이가 N인 직선이다.

세준이는 심판 M명을 적절한 곳에 배치시키려고 한다. 심판은 아무 곳에나 배치시킬 수 있지 않다. 심판은 미리 정해진 K개의 곳에만 위치할 수 있다.

세준이는 심판을 배치할 때, 가장 가까운 두 심판의 거리를 최대로 하려고 한다.

심판을 어디에 배치시켜야 할지 구하는 프로그램을 작성하시오.

 

입력

 

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

 

출력

 

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

 

🧐 핵심 로직

---

1. 레이스 트랙 길이 N, 심판 수 M, 가능한 위치 수 K를 입력받고 K개의 위치를 저장한다.

 

2. 이진 탐색을 통해 가장 가까운 두 심판의 거리를 최대화한다. 초기값으로 최소 거리 min을 1, 최대 거리 max를 N으로 설정한다.

 

3. 중간값 mid를 계산하여 심판 배치 가능성을 확인한다.

 

4. 특정 거리 target를 기준으로 심판을 배치한다. 첫 번째 위치에 심판을 배치하고 이후 위치에 대해 target 거리 이상일 때 심판을 배치한다.

 

5. 가장 최근의 유효한 배치 결과를 출력하며, '1'은 심판이 있는 위치, '0'은 없는 위치를 나타낸다. 여러 해가 가능할 경우, 사전순으로 가장 늦는 배치를 선택한다.

 

💻 최종 코드 (104 ms)

---

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

public class Main {

    static int n, m, k;
    static int[] positions;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

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

        System.out.println(binarySearch());

        br.close();
    }

    private static String binarySearch() {

        String res = "";
        int min = 1;
        int max = n;

        while (min <= max) {

            int mid = (min + max) / 2;
            String ans = possible(mid);

            if (ans.isEmpty()) {
                max = mid - 1;
            } else {
                min = mid + 1;
                res = ans;
            }
        }

        return res;
    }

    private static String possible(int target) {

        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        sb.append(1);
        cnt += 1;
        int before = positions[0];

        for (int i = 1; i < positions.length; i++) {

            if (cnt == m) {
                sb.append(0);
            } else {
                if (positions[i] - before >= target) {
                    sb.append(1);
                    cnt += 1;
                    before = positions[i];
                } else {
                    sb.append(0);
                }
            }
        }

        if (cnt == m) {
            return sb.toString();
        }

        return "";
    }
}