[BJ] 2110 공유기 설치 Java

백준 2110 공유기 설치

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

2110번: 공유기 설치

 

아이디어

• 집의 좌표가 입력으로 최대 10억개 들어올 수 있기에 시간초과에 걸릴 수 있다
• 이진탐색을 사용하면 매번 데이터의 개수를 절반으로 줄일 수 있기 때문에 이분탐색으로 풀어나간다
• 우선 좌표를 오름차순으로 정렬해야 이진탐색 가능
• 공유기 사이의 최소길이는 1이다. 최대길이는 배열의 가장 큰 값이다
• 공유기 배치를 주어진 입력값보다 많이 할 수 있으면 간격을 늘린다
• 입력값보다 적게할 수 있는거면 공유기들 사이의 거리를 더 늘려본다

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        ArrayList<Integer> al = new ArrayList<>();
        for (int i=0; i<n; i++) {
            al.add(sc.nextInt());
        }
        Collections.sort(al);

        // 이진탐색
        // 공유기 사이의 최소거리는 1, 최대 거리는 배열에서의 가장 큰 값(즉 마지막 값)
        int lt = 1;
        int rt = al.get(n-1);
        int answer = 0;

        while (lt <= rt) {
            int mid = (lt+rt) / 2;
            // c개 이상 배치 가능하면 간격을 더 늘려본다
            if (count(al, mid) >= c) {
                answer = mid;
                lt = mid + 1;
            }
            // 그렇지 않다면 간격을 좁힌다
            else rt = mid - 1;
        }

        System.out.println(answer);
    }

    public static int count(ArrayList<Integer> al, int mid) {
        int count = 1; // 공유기 처음 1개 설치
        int pos = al.get(0); // 맨 왼쪽에 있는 곳에 설치해야 최대거리 가능

        for (int i=0; i<al.size(); i++) {
            if (al.get(i) - pos >= mid) {
                count++;
                pos = al.get(i);
            }
        }
        return count;
    }
}