백준 2512번: 예산

백준 2512번: 예산

 

- 이분 탐색 알고리즘을 써야하는 문제입니다. 이분 탐색을 사용하지 않고 상한액을 선형 탐색하면 시간초과에 걸립니다.

- 이분 탐색 알고리즘은 예산의 상한액을 찾을 때 사용됩니다. 입력 받은 예산 요청액들을 배열에 저장한 뒤 sort() 를 통해 오름차순으로 정렬합니다. 예산 상한액은 0부터 배열의 마지막 값(가장 큰 값) 사이를 이분 탐색하면서 찾습니다. 예산 상한액보다 작은 요청액은 그 값을 그대로 더하고 예산 상한액보다 큰 요청액들은 예산 상한액을 더합니다. 총합이 총 예산보다 작을 때를 찾아서 상한액을 반환해주면 됩니다.

 

 

	import java.util.Arrays;
	import java.util.Scanner;
	public class Main{
	public static int binarySearch(int[] a, int t){
	int first = 0;
	int last = a[a.length-1];
	int mid = 0;
	int total = 0;
	while(first <= last){
	mid = (first + last) / 2 ;
	if(calculate(a, mid) > t)
	last = mid - 1;
	else{
	total = mid;
	first = mid + 1;
	}
	}
	return total;
	}
	public static int calculate(int[] a, int b){
	int total = 0;
	for(int i = 0; i < a.length; i++){
	if(b >= a[i])
	total += a[i];
	else
	total += b;
	}
	return total;
	}
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	int total = 0;
	for(int i = 0; i < n; i++) {
	a[i] = sc.nextInt();
	total += a[i];
	}
	int t = sc.nextInt();
	Arrays.sort(a);
	if(total <= t)
	System.out.println(a[a.length-1]);
	else
	System.out.println(binarySearch(a, t));
	sc.close();
	}
	}

view raw BOJ_2512.java hosted with ❤ by GitHub