[백준][C++] 2512: 예산

문제

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

풀이

이분 탐색

 

간단한 이분 탐색 문제. 상한액을 이분 탐색으로 찾으면 된다.

• start를 1, end를 예산요청액 중 최댓값으로 설정한다.
• mid를 (start + end) / 2로 설정한다.
• mid를 상한액으로 설정했을 때의 현재 합계를 구한다.
  • mid보다 작은 예산 요청액은 그대로 sum에 더한다.
  • mid보다 큰 예산 요청액은 mid만큼을 sum에 더한다.
• sum과 M을 비교하여 start와 end 값을 조정한다. 
• start가 end를 넘을 때까지 진행한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory.h>
#include <unordered_map>
#include <cmath>
#include <deque>
#include <climits>
#include <sstream>
#include <cstdlib>

using namespace std;

int nums[10'000];
int M;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	int maxi = 0;

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> nums[i];

		maxi = max(maxi, nums[i]);
	}

	cin >> M;

	// 예산의 범위는 1부터 최대 예산요청액
	int start = 1;
	int end = maxi;
	int answer = 0;
	while (start <= end)
	{
		int mid = (start + end) / 2;

		int sum = 0;

		// 현재 합계 계산
		for (int i = 0; i < N; ++i)
		{
			// 상한액만큼이 현재 sum에 들어간다.
			sum += min(mid, nums[i]);
		}

		// 현재 합계와 총 예산을 비교
		if (sum > M)
		{
			end = mid - 1;
		}
		else
		{
			answer = mid;
			start = mid + 1;
		}
	}

	cout << answer;

	return 0;
}