[백준 2512] 예산

 

 

나무 자르기 문제와 거의 유사한 문제이다.

예산을 더하는 로직만 약간 다를뿐 이분탐색으로 접근하면 된다.

 

 

코드 1

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n];
        long sum = 0;
        int max = 0;
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            if(max < a[i])
                max = a[i];
            sum += a[i];
        }
        int m = sc.nextInt();
        
        if(sum <= m) System.out.println(max);
        else {
            int low = 0;
            int high = 1000000000;
            while(low + 1 < high) {
                int mid = (low + high)/2;
                sum = 0;
                for(int i=0; i<n; i++) {
                    if(a[i] < mid) sum += a[i];
                    else sum += mid;
                }
                if(sum <= m) low = mid;
                else high = mid;
            }
            System.out.println(low);
        }
    }
}

 

예산의 총합이 m 보다 작으면 예외처리를 따로 해주어야 한다. 이것 때문에 5번은 틀렸다;;

 

 

코드 2

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n];
        int max = 0;
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            if(a[i] > max) max = a[i];
        }
        int m = sc.nextInt();
        
        int low = 0;
        int high = max;
        while(low <= high) {
            int mid = (low + high)/2;
            long sum = 0;
            for(int i=0; i<n; i++) {
                if(a[i] < mid) sum += a[i];
                else sum += mid;
            }
            if(sum <= m) low = mid + 1;
            else high = mid - 1;
        }
        System.out.println(high);
    }
}

 

아래 코드가 좀 더 깔끔하다.