Q 11973 Angry Cows (Silver)

💡 문제 요약 및 분석

일직선상으로 놓여진 건초 더미가 있고, x 위치에 있는 소 한 마리가 r만큼의 범위로 건초를 먹는다. (x-r ~ x+r) 주어진 모든 건초 더미를 파괴하기 위한 최소 파괴력 r 을 구하자.

💡 알고리즘 설계

✅ 핵심 아이디어 : 이분 탐색으로 풀 수 있다. 문제에서는 최소 파괴력 r 에 대해서만 묻고 있으므로 x 까지 찾아낼 필요는 없다.

1. 입력

   • 표준입력으로 int N, int K 저장한다.
   • 표준입력으로 건초 더미의 위치를 int[N] bales 배열에 저장한다.
   • 배열을 오름차순 정렬한다.

2. 연산

   • left = 0, right = bales[N-1]
   • 중간값 mid를 계산한다. mid = (left + right) / 2
   • 계산을 위한 x, count 값을 세팅한다. x = bales[0] + mid; x = 소의 위치로, (x - mid ~ x + mid) 범위를 체크하게 될 것이다. count 변수는 소가 몇 마리 필요한지 세기 위해 필요하다.
   • ((x - mid) <= bales[i] && balse[i] <= (x + mid)) 범위의 값을 체크한다. 위 조건에 포함되지 않는 else 의 경우라면 첫 번째 소의 파괴 범위를 넘어선 것이므로 새로운 x를 세팅하고 count++ 한다.
   • 다음과 같은 경우의 수가 있다. count > K : left = mid + 1; count <= K : right = mid - 1; result = mid;

3. 출력

   • result 변수를 출력한다.

💡 코드

import java.util.Arrays;

public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args)  throws Exception {
        int N = read();
        int K = read();
        int[] bales = new int[N];
        for (int i = 0; i < N; i++) {
            bales[i] = read();
        }
        Arrays.sort(bales);

        int left = 0;
        int right = bales[N - 1];
        int result = 0;

        while (left <= right) {
            int mid = (left + right) / 2;
            int x = bales[0] + mid;
            int count = 1;

            for (int i = 0; i < N; i++) {
                if ((x - mid) <= bales[i] && bales[i] <= (x + mid)) {
                    // 아무런 작업도 하지 않음
                } else {
                    x = bales[i] + mid;
                    count++;
                }
            }

            if (count > K) {
                left = mid + 1;
            } else {
                right = mid - 1;
                result = mid;
            }
        }

        System.out.println(result);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n * log max)	O(n)