[백준 2512번] 예산

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

2512번: 예산

이 문제는 이진 탐색을 이용한 문제입니다

---

풀이법

이진 탐색을 이용하는 방법은 다음과 같습니다

1. 무조건 가능한 수 중에 최소값 start 변수로 지정
2. 가능 여부를 떠나 , 현재 최대값을 end 변수로 지정
3.중간 값mid 를 찾은 다음 그 중간값에 따라 값을 바꿨을 때, 조건에 맞는 지 확인
4.조건에 맞는다면 이 중간값을 start 변수에 대입, 아니면 end 변수에 대입합니다
5.mid 가 start 또는 end와 같아지면 탐색을 종료 하고 해당 mid 값을 찾습니다.

이 방법을 반복해 배정된 예싼들 중 최댓값을 찾을 수 있습니다

코드

---

import java.util.*;
public class Main {
	public static void main(String arg[]) {
		Scanner sc= new Scanner(System.in);
		int n=sc.nextInt();
		int []locals=new int[n];
		int first_sum=0;
		for(int i =0;i<n;i++) {
			locals[i]=sc.nextInt();
			first_sum+=locals[i];
		}
		int max_budget=sc.nextInt();
		Arrays.sort(locals);
		if(first_sum<=max_budget)
			System.out.println(locals[n-1]);
		else
			System.out.println(sol(0,locals[n-1],max_budget,locals));
	}
	public static int sol(int start,int end, int max_budget,int[]locals) {
		int mid=(start+end)/2;
		int sum=0;
		if(mid==end || mid==start) {
			return mid;
		}else {
			for(int i=0;i<locals.length;i++) {
				if(locals[i]>mid) {
					sum+=mid;
				}else {
				sum+=locals[i];
				}
			}
			if(sum>max_budget)
				end=mid;
			else if (sum<max_budget)
				start=mid;
			else
				return mid;
			return sol(start,end,max_budget,locals);
		}
	}

}