[JAVA] 백준 2512번 - 예산

 

이 문제는 이분탐색을 통해 해결이 가능했다

이분 탐색의 기준은 인덱스가 아닌 예산이 된다

예산을 기준으로 시행하며 만약 m이 예산의 합보다 작으면 임계치(mid)를 1 감소하고, m이 더 크면 예산 배정이 더 가능한지 확인해야 하니까 1을 더해서 확인해본다

처음엔 좀 어려웠는데 2번 푸니까 이해가 간다!

아래는 코드!

 

 

자바 코드)

import java.util.Arrays;
import java.util.Scanner;

public class boj2512 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer=0;
        int n = sc.nextInt();
        int[] budgets = new int[n];
        for(int i=0;i<n;i++) {
            budgets[i] = sc.nextInt();
        }
        int m = sc.nextInt();

        Arrays.sort(budgets);
        int low = 0;
        int high = budgets[n-1];

        int mid = 0;
        while(low<=high) {
            long sum = 0;
            mid = (low+high)/2;

            for(int budget : budgets) {
                if(mid < budget) {
                    sum += mid;
                } else {
                    sum += budget;
                }
            }

            if(sum>m) { //예산 초과
                high = mid-1;
            } else {
                low = mid+1;
                answer = mid;
            }
        }
        System.out.println(answer);
    }
}