[백준/Java] 2512 예산

조건

1. 지방의 수 N개 주어진다. (3 <= N <= 10,000)

2. 각 지방마다 요청하는 예산이 N개 만큼 주어진다. (1 <= 예산 <= 100,000)

3. 총 예산이 주어진다.(최대 값은 10억이다)

예제 입력

해설

이 문제는 이분탐색으로 해결 할 수 있는데 범위는 예산을 요청한 값들중에 가장 큰 값을 넣으면 된다. 각 지방마다 요청하는 예산 값이 총 예산보다 낮아야 하기 때문에 범위의 최대값이 예산들 값중에서만 제일 크면 된다. 그 후 전체 예산을 탐색하며 mid 값 vs 요청예산 둘 중에서 낮은 값을 넣어 sum 값이 전체 예산을 초과하는지 확인하면 된다.

코드

import java.io.*;
import java.util.*;



public class Main {
	
	static int N,M;
	static int[] A;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		
	N = scan.nextInt(); // 지방의 수를 받는다.
	A = new int[N + 1]; // index를 1부터 시작하기 위해 +1을 해준다.
	for(int i=1;i<=N;i++) {
		A[i] = scan.nextInt(); // 지방이 요청하는 예산을 받는다.
	} 
	M = scan.nextInt(); //총 예산을 받는다.
	}

	
	static boolean findAns(int buget) {
		int sum = 0;
		for(int i=1;i<=N;i++) {
			 sum += Math.min(A[i],buget); // 요청 예산과 mid을 비교하여 더 낮은 값을 								//넣어주고 sum을 해 총 예산보다 작다면 true를 반환한다.
		}
		return sum <= M;

	}
	

	static void find() {
	int ans =0, L =0, R = 0; 
	for(int i =1;i<=N;i++) {
		R = Math.max(R, A[i]); // 탐색 범위의 최대값은 요청 예산에서 제일 큰값으로 해주							   // 다
	}
	while(L <= R) {
		int mid = (L + R) / 2;
		if(findAns(mid)) {
			ans = mid; //true이면 ans에 mid값을 넣고
			L = mid + 1; // 범위를 줄여준다.
		} else {
			R = mid - 1;
		}
	}
	System.out.println(ans);
		}

		
		
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}