2512 예산

처음에는 limit의 평균을 구해서, 넘는 값에 대해 적정 선을 맞추는 방식으로 했는데 틀렸음

이 문제는 '이분탐색'으로 풀어야되는 문제임

일부 테스트케이스는 맞았지만, 실제로는 틀렸음

import java.io.*;
import java.util.*;
import javax.swing.Icon;

public class Main {
    public static void main(String[] args) throws IOException {
        /*
         * 총액 이하에서 가능한 한 최대의 총 에싼을 배정
         *
         * 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정
         * 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여, 그 이상인 예상 요청에는 모두 상한액을 배정
         * 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정
         *
         * o(n)으로 풀어야함
         *
         * 520 - 485 = 35 오바
         * 485 ->
         * 121
         * -1, -11, +19, + 29
         * - 12 / 남은 개수
         * 평균보다 6씩 더주기
         * +48 인 상황인데
         * */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        PriorityQueue<Integer> numbers = new PriorityQueue<>(Comparator.reverseOrder());

        int total = 0;
        for (int i = 0; i < n; i++) {
            int number = Integer.parseInt(st.nextToken());
            numbers.add(number);
            total += number;
        }

        int limit = Integer.parseInt(br.readLine());

        if (limit >= total) {
            System.out.println(numbers.remove());
            return;
        }

        int limitAvg = limit / n;
        int overCount = 0;
        int underScore = 0;

        int under = 0;
        while (!numbers.isEmpty()) {
            int number = numbers.remove();

            if (number > limitAvg) {
                overCount++;
            } else {
                int temp = limitAvg - number;
                underScore += temp;
                under += number;
            }
        }
        int result = limitAvg + (underScore / overCount);
        if (overCount == n) {
            System.out.println(limitAvg);
            return;
        }
        System.out.println(result);
    }
}

계속해서 최적의 해를 찾아가는 것이기 떄문에 적절함

• 초안
  최적화 하지 않았음

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 n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] requests = new int[n];

        for (int i = 0; i < n; i++) {
            requests[i] = Integer.parseInt(st.nextToken());
        }

        int limit = Integer.parseInt(br.readLine());

        Arrays.sort(requests);

        int answer = 0;
        int left = 0;
        int right = requests[requests.length - 1];

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

            for (int request : requests) {
                sum += Math.min(request, mid);
            }

            if (sum <= limit) {
                left++;
                answer = Math.max(answer, mid);
            } else {
                right--;
            }
        }
        System.out.println(answer);
    }
}

• 최적화 ver
  mid보다 큰 애들은 상한값 처리 하고, 나머지는 누적합처리해서 계속해서 계산해야되는 부분을 최적화했음

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 n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] requests = new int[n];
        int max = 0;
        int total = 0;

        for (int i = 0; i < n; i++) {
            int number = Integer.parseInt(st.nextToken());
            requests[i] = number;
            max = Math.max(max, number);
            total += number;
        }

        int limit = Integer.parseInt(br.readLine());

        if (limit >= total) {
            System.out.println(max);
            return;
        }

        Arrays.sort(requests);

        int left = 0;
        int right = requests[requests.length - 1];
        int answer = 0;
        int[] sumArr = new int[n];

        for (int i = 0; i < n - 1; i++) {
            sumArr[i + 1] = sumArr[i] + requests[i];
        }

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

            int idx = underScore(requests, mid);
            int sum = sumArr[idx] + (mid * (n - idx));

            if (sum <= limit) {
                answer = mid;
                left = left + 1;
            }
            else {
                right = right - 1;
            }
        }
        System.out.println(answer);
    }

    public static int underScore(int[] requests, int target) {
        int left = 0;
        int right = requests.length - 1;

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

            if (requests[mid] <= target) {
                left++;
            } else {
                right = mid;
            }
        }
        return left;
    }
}