Baekjoon 2512 예산

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

결과 2148 KB / 0 ms

출처 BOJ

언어 C++ 17

 

풀이

이분탐색에 기반한 문제 풀이

0 ~ 최대값 사이에서 이분탐색을 진행하며 조건에 맞는 값을 계산한다.

입력된 총 예산을 기준으로 범위를 수정해가며 이분탐색이 종료될까지 진행한다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

int getMax(vector<int> inputs) {
	int res = 0;
	for (int i = 0; i < inputs.size(); i++)
		if (res < inputs[i])
			res = inputs[i];
	return res;
}

int getSum (vector<int> inputs, int mxm)
{
	int res = 0;
	for (int i = 0; i < inputs.size(); i++)
		if (inputs[i] <= mxm)
			res += inputs[i];
		else
			res += mxm;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin >> n;
	vector<int> inputs(n); 	for (int i = 0; i < n; i++) cin >> inputs[i];
	int mxm; cin >> mxm;

	int left = 0, right = getMax(inputs);

	while (left <= right) {
		int mid = (left + right) / 2;

		if (getSum(inputs, mid) > mxm)
			right = mid - 1;
		else
			left = mid + 1;
	}

	cout << right;

	return 0;
}