백준 2512. 예산

백준 2512. 예산

이분탐색 문제

그런데 조건이 조금 추가됨

1. 간단 설명

---

1. 모든 요청이 배정될 수 있는 경우에는, 요청 금액을 그대로 배정함

2. 모든 요청이 배정될 수 없는 경우, 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정함 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정한다

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때,

위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성

2. 예제

---

4
120 110 140 150
485

전체 국가 예산은 485이고

4개의 지방에서 각각 120, 110, 140, 150을 요청한 상황

상한액을 127로 잡으면 위의 요청들에 대해서

120, 110, 127, 127 총 484로 가능한 최대가 됨

3. 알고리즘

---

1. 데이터를 정렬할 수 있다 -> 요청 예산 순으로 정렬

2. 답이 하나 혹은 하나의 범위 내에서 결정됨 -> 하나의 정수

3. 검색 대상이 10억 이상으로 매우 크다 -> 총 예산은 최대 10억까지 가능

이므로 이분탐색 문제로 판단

1. N 입력받고 요청 예산들을 province 벡터에 저장
2. 총 예산 M 입력받기
3. 이분 탐색으로 최적 예산 찾기
	3-1. l=0, r=M으로 놓고 시작
	3-2. l<r 인 경우 반복
		3-2-1. mid = (l+r)/2 를 놓고, mid만큼 각 지방에 예산 할당
		3-2-2. mid 보다 요청한 예산이 적은 경우, 그만큼만 할당함
		3-2-3. 그보다 많은 경우, mid 만큼만 할당
		3-2-4. 전체 할당된 예산을 확인 후, M과 비교
			3-2-4-1. 전체 할당된 예산이 남는다면 l = mid + 1
			3-2-4-2. 전체 할당된 예산이 모자르다면 r = mid - 1
4. 최적 예산 출력

특정한 정수 상한액 x를 계산하여

그 이상인 예산요청에는 모두 상한액을 배정

상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정하면 된다

1. 이분 탐색의 시작 지점 최대, 최소를 어떻게 잡고 시작할건지?

A. 가능한 할당 예산의 범위는 0 ~ M이므로 , l = 0, r = 요청 예산 중 최대값

1. l, r 갱신 판단을 어떻게 할건지?

A. mid 만큼 예산할당 시, 초과된다면 예산이 초과되므로 r을 mid -1로 조정

예산이 남는다면 예산을 더 줘도 되므로 l을 mid + 1 로 조정

4. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> province;

int MyBinarySearch() {

	int l = 0, r = *max_element(province.begin(), province.end()); // max_element 를 사용해 최대값 찾기
	int result = 0;

	while (l <= r) {
		int mid = (l + r) / 2;

		// 예산 할당해봄
		int total = 0;

		for (int e : province) {
			total += min(e, mid); 
			// 요청한 예산보다 mid가 크다면 요청 예산만큼만, 
			// 요청한 예산보다 적다면 mid 만큼만 할당함
		}

		if (total <= M) {
			result = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	
	return result;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N; 
	province.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> province[i];
	}
	cin >> M;

	cout << MyBinarySearch();

	return 0;
}

최적 예산의 상한선을 이분탐색으로 찾는 문제이므로

알고리즘 헤더의 lower_bound, upper_bound는 사용 불가능하므로, 직접 구현해야하는 문제였다

이 함수들은 특정 값 이상, 초과하는 첫 번째 원소의 위치를 리턴하므로, 값의 상한선을 찾는데는 부적절하다