[백준] 20917: 사회적 거리 두기

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

 

풀이

솔브드에 랜덤 마라톤 기능이 생겼다. 일주일마다 8문제를 랜덤으로 골라주는데, 풀 문제를 따로 고르지 않아 편한 점이 있다.

 

이 문제도 랜덤 마라톤에 있는 문제였다.

 

좌석들의 위치가 주어지고, 좌석을 s개 선택할 때 거리의 최댓값을 구해야한다.

 

좌석들의 위치를 입력받아 정렬했다.

 

서로 떨어진 거리를 기준으로 이분탐색을 하는데,

 

이때 일정 거리(mid)를 기준으로 좌석의 위치 배열을 앞에서부터 탐색하면서 배치할 수 있는 좌석의 개수를 헤아린다.

 

좌석의 개수가 원하는 개수보다 적다면 `high`를 `mid -1`로 배치하고,

 

원하는 개수 이상이라면 `mid`값을 `result`에 넣고, `low`를 `mid +1`로 늘려 더 큰 거리에서 다시 탐색한다.

 

최종적으로 결정된 result값이 답이 된다.

 

---

 

메모리: 211396KB
시간: 1692ms
언어: Java 11

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));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            int[] dist = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                dist[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(dist);

            int answer = pickDistance(dist, n, s);
            sb.append(answer).append("\n");
        }

        System.out.println(sb);
    }

    private static int pickDistance(int[] dist, int n, int s) {
        int low = 0;
        int high = dist[n - 1] - dist[0];

        int result = 0;
        while (low <= high) {
            int mid = (low + high) / 2;

            int cnt = 1;
            int prev = dist[0];
            for (int i = 1; i < n; i++) {
                if (dist[i] - prev >= mid) {
                    prev = dist[i];
                    cnt++;
                }
            }

            if (cnt < s) {
                high = mid - 1;
            } else {
                result = mid;
                low = mid + 1;
            }
        }

        return result;
    }

}