백준 2512 c++ "예산" -PlusUltraCode-

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

[필자 사고]

이분 탐색 문제이다.

이분 탐색인지 아닌지를 떠오르는 과정이 중요한다.

해당 문제는 정렬되어 있고 정해진 범위가 있고 거기서 특정 숫자를 찾는 과정이다.

이 정도의 힌트로 이분탐색을 유추할 수 있어야 한다.

 

이 문제만의 특별한 점은 이분탐색에서 sum을 계산하는 방식이 min(arr[i],mid) 이정도?? 

 

아래는 자세한 코드 해설이다.

[코드 해설]

Input() 함수

• 사용자로부터 정수 N을 입력받는다. 이는 예산을 요청한 지역(또는 항목)의 개수이다.
• arr 벡터에 N개의 예산 요청 금액을 입력받는다.
• 마지막으로 전체 예산 총액 M을 입력받는다.

이 함수는 예산 요청 리스트와 총 예산을 입력받아 문제 해결을 위한 초기 데이터를 준비한다.

---

Game_Start() 함수

• 예산 배정의 상한선을 이분 탐색을 통해 찾는다.
• 이분 탐색의 범위는 0부터 요청 금액 중 가장 큰 값까지이다.
  • low는 0
  • high는 arr 내 최대값
• 반복적으로 다음을 수행한다:
  1. 중간값 mid를 상한선 후보로 잡는다.
  2. 각 요청 금액과 상한선을 비교하여 min(arr[i], mid)만큼 예산을 배정하고, 그 총합을 sum에 누적한다.
     • 이는 각 지역이 요청한 금액보다 많이 배정되지 않도록 하는 역할이다.
  3. 총 배정 금액 sum이 M 이하라면:
     • 현재 상한선 mid는 가능한 후보이므로 answer에 저장한다.
     • 더 높은 상한선도 가능한지 확인하기 위해 low 값을 증가시켜 탐색 범위를 오른쪽으로 이동한다.
  4. 반대로 sum이 M을 초과하면:
     • 상한선을 낮추기 위해 high 값을 줄인다.
• 반복이 끝난 후, 최적의 상한선 answer를 출력한다.

이 함수는 전체 예산 M을 넘지 않으면서도 각 항목에 최대한 많은 금액을 배정할 수 있는 상한선을 효율적으로 찾아낸다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> arr;
int M;

void Input() {
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	cin >> M;
}

void Game_Start() {
	int low = 0;
	int high = *max_element(arr.begin(), arr.end());
	int answer = 0;
	while (low <= high) {
		int mid = (low + high) / 2;
		int sum = 0;

		for (int i = 0; i < N; i++) {
			sum += min(arr[i], mid);
		}

		if (sum <= M) {
			answer = mid;
			low = mid+1;
		}
		else {
			high = mid - 1;
		}

	}
	cout << answer;
}



int main(void) {
	Input();
	Game_Start();
}