(백준) 제기차기 _ 23830

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

 

🐢 설명

아주 간단한 이분탐색 문제이다. 결국 K를 찾기 위해 가능한 범위를 지정한 후 해당 범위내에서 K값을 지정해보고 이때의 평균값과 선생님이 원하는 S값과의 비교를 통해 범위를 조정해가면 된다.

 

평균을 높이기 위해서는 결국 K를 올려야 하므로 left = mid + 1, 평균을 낮추기 위해서는 K를 낮추기 위해 right = mid 로 해주면 된다. 가능한 가장 작은 K를 구해달라 하였으므로 lower bound로 구하면 된다.

 

여기서 놓칠 수 있는 부분은 문제의 첫 문장에 양의 정수 K라고 하였으므로 K의 하한 범위를 0이 아닌 1로 잡아줘야 한다.

 

🐢코드

public class 제기차기_23830 {
    static int N;
    static int[] point;
    static int p;
    static int q;
    static int r;
    static long S;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        point = new int[N];

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

        st = new StringTokenizer(br.readLine());
        p = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        S = Long.parseLong(st.nextToken());

        binarySearch();
    }

    private static void binarySearch() {
        int left = 1;
        int right = 110000;
        int mid;

        while (left < right) {
            mid = (left + right) / 2;

            long avg = calc(mid);
            if (avg < S)
                left = mid + 1; // 평균 높여야 댐. -> K 키움
            else {
                right = mid; // 최대한 낮춘다. -> K 낮춤
            }
        }
        if (right == 110000) System.out.println(-1);
        else System.out.println(right);
    }

    private static long calc(int mid) {
        long sum = 0;
        for (int myPoint : point) {
            if (myPoint > mid + r) sum += myPoint - p;
            else if (myPoint < mid) sum += myPoint + q;
            else sum += myPoint;
        }
        return sum;
    }
}

 

🐢 마무리