예산 - 2512

문제

풀이

import java.util.*;

// 예산
public class ex2512 {

    static int n;
    static int[] arr;
    static int total;

    public static long solution(int sum){
        int answer=0;
        Arrays.sort(arr);

        // 총 예산 = total
        long lt = 0;
        long rt = arr[n-1];
        while (lt<=rt){
            long mid = (lt + rt) / 2;
            long budget = 0;

            for(int i=0; i<n; i++){
                if(mid >= arr[i]){
                    budget += arr[i];
                }
                else if(mid < arr[i]){
                    budget += mid;
                }
            }

            if(budget <= total) lt = mid + 1;
            else rt = mid - 1;
        }

        return rt;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];

        int sum=0;
        int max =Integer.MIN_VALUE;
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
            sum+=arr[i];
            max = Math.max(max,arr[i]);
        }
        total = sc.nextInt();

        if(sum <= total) System.out.println(max);
        else System.out.println(solution(sum));
    }
}

이분 탐색은 풀 때마다 헷갈린다. 그냥 문제 보고 종이에 쓱쓱 쓰다 보니까 이분탐색 문제인거를 바로 알았다.

이분탐색 필수조건

1. 좌표의 정렬
2. mid 값 구하기 -> mid 값을 기준으로 로직 실행.
3. 만약 mid값 기준으로 더 작은 값이 필요하다면 rt = mid - 1; 그 반대라면 lt = mid + 1;
4. 무한 반복 (효율좋음)

이분탐색 문제 개인적으로 어렵게 느껴지는데 간단한 문제는 위 필수조건 적용해서 꼭 풀자.