[알고리즘] 백준 2512 예산 -이분탐색- 자바

 

 

www.acmicpc.net/problem/2512

2512번: 예산

 

 

 

 

백준 이분탐색 유형 문제입니다. 

지방마다 갖고 있는 예산이 다른데 국가에서 총 예산 M 이하를 걷으려고합니다.

총 M이하의 예산이하라는 조건에서 지방마다 최대 얼마를 걷을 수 있는지 구하는 문제입니다.

 

N의 개수를 보아 완전탐색으로 풀면 시간초과가 뜰겁니다. 이분탐색으로 풀어야합니다.

 

이분탐색에서 

left 는 0 (최소 예산)

right 는 지방예산중 가장 큰 금액 (최대 예산)

으로 하여 탐색을 시작합니다.

 

풀이에 주석을 충분히 작성했습니다. 다음과 같습니다.

 

[Java]

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

class Main {
    private static int[] arr; // 지방 예산
    private static long answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 지방의 수
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        long M = sc.nextLong(); //총 예산
        long left = 0;
        long right = arr[N-1];
        while (left <= right) {
            long mid = (left + right) / 2; //내야할 세금
            long sum = 0; // 모든 지방 세금 합
            for (int money : arr) {
                if (money >= mid) sum += mid; //내라는 세금 낼 수 있는 지방
                else sum += money; //못내는 지방은 가진 최대 돈만 냄
            }
            if (sum > M) { // 내라는 세금 보다 많은 경우 -> 세금을  줄여본다.
                right = mid - 1;
            } else { // 내라는 세금보다 적은 경우 -> 세금을 높여서 더 최고의 경우의 수를 찾는다.
                left = mid + 1;
                answer = Math.max(answer, mid);
            }
        }
        System.out.println(answer);
    }
}

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!