[백준 2512] 예산 - JAVA

https://www.acmicpc.net/problem/2512

이분탐색

 

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

sum <=  total이면 max를 출력한다.

 

2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

 

이분 탐색한다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    int T = Integer.parseInt(br.readLine());

    int sum = 0;
    int max = 0;

    for (int i = 0; i < N; i++) {
      sum += arr[i];
      max = Math.max(arr[i], max);
    }

    if (sum <= T) {
      System.out.println(max);
      return;
    }

    int l = 0;
    int r = max;
    int ans = 0;

    while (l <= r) {
      int mid = (l + r) >>> 1;
      int midVal = 0;

      for (int i = 0; i < N; i++) {
        midVal += Math.min(mid, arr[i]);
      }

      if (midVal <= T) {
        ans = Math.max(ans, mid);
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }

    System.out.println(ans);
  }
}