백준 2512 예산(Java)

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

2512번: 예산

---

 

해석 및 팁

 

---

 

이 문제는 이분탐색을 활용하는 문제입니다. 먼저 요구예산이 전체 예산보다 작으면 그대로 최댓값을 출력해 주면 됩니다. 요구예산의 합이 국가예산보다 클 경우에는 이분탐색을 통해 상한액을 구해주면 되는 문제입니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    
    int n = sc.nextInt();
    int[] arr = new int[n];
    
    int sum = 0;
    int max = -1;
    
    for(int i = 0; i < n; i++) {
      int num = sc.nextInt();
      arr[i] = num;
      sum += num;
      max = Math.max(max, num);
    }
    
    int m = sc.nextInt();

    if(sum <= m) sb.append(max);
      
    else {
      int l = 0;
      int r = max;
      
      while(l <= r) {
        
        int result = 0;
        int mid = (l + r) / 2;
        
        for(int i = 0; i < n; i++) {
          if(arr[i] < mid) result += arr[i];
          else result += mid;
        }
        
        if(result <= m) l = mid + 1;
        else r = mid - 1;
      }
      
      sb.append(r);
    }

    System.out.println(sb);
  }
}