백준 2110번
https://www.acmicpc.net/problem/2110

문제

---

생각하기

---

• 이분 탐색 문제이다.

  • 가장 인접한 두 공유가 사이의 최대 거리를 구하면 된다.
  • 이분 탐색을 통해서 공유기 사이의 거리를 좁혀가면서 최적의 해를 구하면 된다.
  • mid값을 거리로 설정해서

• 재귀를 통해서 구현했다.

동작

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        // 최소거리가 가질 수 있는 최솟값
        int low = 1;
        int high = arr[N - 1] - arr[0] + 1;

        sb.append(binarySearch(low, high) - 1);

집의 좌표를 배열에 저장하고, 거리 계산을 위해서 정렬을 해준다.

low 는 최소거리 1로 설정하고, high는 최대거리로 arr의 최대값과 최소값의 거리에서 + 1로 해준다.

그리고 이분 탐색 메소드 실행 여기서 최소값을 구해야 하므로 결과값에 -1을 해주어야 한다.

    private static int binarySearch(int low, int high) {
        if (low > high) {
            return -1;
        }

        int mid = (low + high) / 2;

        if (check(mid) < C) {
            // 필요한 공유기 설치 개수가 C보다 클 경우,
            // 최소 거리를 더 늘려야 함.
            high = mid - 1;
            int result = mid;

            int temp = binarySearch(low, high);
            if(temp == -1) {
                return result;
            } else {
                return temp;
            }
        } else {
            low = mid + 1;
            return binarySearch(low , high);
        }
    } // End of binarySearch

재귀를 통해서 이분탐색을 진행한다.

low가 high보다 커졌을 때는 -1을 return하고, 마지막에 -1이 return 될 때는 mid를 return하는 형식으로 진행한다.

코드

---

Java

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int C;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;


        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        // 최소거리가 가질 수 있는 최솟값
        int low = 1;
        int high = arr[N - 1] - arr[0] + 1;

        sb.append(binarySearch(low, high) - 1);
        bw.write(sb.toString());
        bw.close();
    } // End of main

    private static int binarySearch(int low, int high) {
        if (low > high) {
            return -1;
        }

        int mid = (low + high) / 2;

        if (check(mid) < C) {
            // 필요한 공유기 설치 개수가 C보다 클 경우,
            // 최소 거리를 더 늘려야 함.
            high = mid - 1;
            int result = mid;

            int temp = binarySearch(low, high);
            if(temp == -1) {
                return result;
            } else {
                return temp;
            }
        } else {
            low = mid + 1;
            return binarySearch(low , high);
        }
    } // End of binarySearch

    private static int check(int dist) {
        int count = 1;
        int lastLocate = arr[0];

        for (int i = 1; i < N; i++) {
            int locate = arr[i];

            // 이전 집과 현재 집의 거리가 최소 거리보다 크거나 같으면 공유기 개수를 증가
            if (locate - lastLocate >= dist) {
                count++;
                lastLocate = locate;
            }
        }

        return count;
    } // End of check
} // End of Main class