[C++]백준2512번 예산

오늘은 백준2512번 예산 문제를 풀어보도록 하자. 이분탐색 문제는 항상 적응하기가 힘들다. 예외처리를 생각할게 많은 것 같다. 더 많은 문제를 풀어보아야겠다.

문제는 다음과 같다.

                               [접근법]

  1. 분배할 수 있는 예산의 최댓값을 구하는 문제이다. 필요한 예산이 120 110 140 150 이고 총 예산이 485이면 127씩 분배해서 484로 줄 수 있는 것이 최대이다.
  
  2. 우선 이분탐색을 하기 위해 배열이 정렬되어 있어야 한다. 정렬을 해준 후, s = 0, e = arr[arr.size()-1], mid = (s+e)/2 로 놓는다.
  
  3. 그 후 만일 예산 초과면 e = mid -1 , 예산이 남으면 s = mid + 1을 해주면서 이분탐색을 진행한다.
  
  4. 만일 예산이 맞다면 break을 해주고 mid출력.

                                     [코드]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>arr;
int N, num, money;
bool flag = false;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	cin >> money;
	
	int s = 0, e = arr[arr.size() - 1], sum = 0;
	long long mid;

	while (s <= e) {
		sum = 0;
		mid = (s + e) / 2;
		for (int i = 0; i < N; i++) {
			if (mid >= arr[i]) {
				sum += arr[i];
			}
			else {
				sum += mid;
			}
		}
		if (money > sum) {
			s = mid + 1;
		}
		else if(money < sum){
			e = mid - 1;
		}
		else {
			flag = true;
			break;
		}
	}
	if(flag)cout << mid;
	else cout << s-1;
}