자바(백준) 2512 예산

오답 노트 & 새로 알게 된 점

해당 문제는 매개 변수 탐색 방법을 사용하면 된다.

 

정해진 총액 이하에서 가능한 최대의 총 예산을 구해라

-> 예산이 n일 때, 정해진 총액을 만족하느냐를 구하면 된다.

 

여기서 이분 탐색을 실시할 때, e값을 생각해보아야한다.

만약에 e를 M의 최댓값인 10억이라고 잡는다면, 예제 입력2와 같이

총 나라의 예산을 합쳐도 총합 예산보다 작다면 상한액을 10억이라할 수 있기 때문이다.

즉, 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정하면 된다.

 

---

코드

package Week10;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N; //지방 수
    static int M; //총 예산
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
        A = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = atoi(st.nextToken());
        }
        M = atoi(br.readLine());
 
        paraSearch();
    }
 
    //target은 상한액을 의미한다.
    static boolean possible(int target) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if(A[i] > target) sum += target;
            else sum += A[i];
        }
 
        return sum <= M;
    }
 
    static void paraSearch() {
        int s = 0, e = 0, rel = 0;
        for (int i = 0; i < N; i++) e = Math.max(e, A[i]);
        //최댓값은 금액들의 최댓값이어야한다.
        while (s <= e) {
            int mid = (s + e) / 2;
 
            if (possible(mid)) {
                rel = mid;
                s = mid + 1;
            }
            else e = mid - 1;
        }
        System.out.println(rel);
    }
}
 
/**
 * 정해진 총액 이하에서 가능한 한 최대의 총 예산을 구해라
 * -> 예산이 n일 때, 정해진 총액을 만족하느냐?
 *
 */