백준(BOJ) 2512 : 예산 (실버2) / 자바(Java) 풀이

문제

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

3줄 요약

1. 지방의 수 N, 각 지방의 예산요청 A, 총 예산 M을 입력받습니다. 이분 탐색의 범위를 설정하기 위해 예산요청 중 최댓값에 1을 더해 상한값으로 사용합니다. 이는 모든 예산요청이 상한액과 같은 경우를 포함하기 위함입니다.
2. 이분 탐색을 사용하여 상한액을 조정해가며 총 예산이 M 이하가 되는 최대 상한액을 찾습니다. 이는 Upper Bound를 찾는 과정으로, 조건을 만족하는 최댓값을 찾습니다.
3. Upper Bound로 찾은 값은 조건을 만족하는 최솟값보다 1 큰 값이므로, 최종 결과에서 1을 빼줍니다. 이렇게 얻은 값이 실제로 배정 가능한 최대 예산이 됩니다.

코드

// package boj2512;

import java.io.*;
import java.util.Arrays;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        // System.setIn(new FileInputStream("src/input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 지방의 수 N 입력받기
        int N = Integer.parseInt(br.readLine());
        
        // 각 지방의 예산요청 A 입력받기
        int[] A = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        
        // 총 예산 M 입력받기
        int M = Integer.parseInt(br.readLine());
        
        br.close();
        
        // 이분 탐색 범위 설정
        int s = 1;
        int e = Arrays.stream(A).max().getAsInt() + 1;
        
        // 이분 탐색 수행
        while (s < e) {
            int mid = (s + e) / 2;
            
            // 상한액이 mid일 때 총 예산 계산
            int totalBudget = getTotalBudget(A, mid);
            
            if (totalBudget <= M) {
                s = mid + 1;
            } else {
                e = mid;
            }
        }
        
        // 결과 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(e - 1));
        bw.flush();
        bw.close();
    }
    
    // 상한액이 limit일 때 총 예산 계산 메서드
    private static int getTotalBudget(int[] budgets, int limit) {
        int total = 0;
        for (int budget : budgets) {
            total += Math.min(budget, limit);
        }
        return total;
    }
}