[알고리즘] C++ 백준 2512 예산

백준 2512

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

2512번: 예산

풀이 전 나의 생각

예산이 담긴 M의 배열이 주어질 때 국가예산의 총액에서

최대로 예산을 배정할 수 있는 상한액을 구해야한다.

 

조건

- N은 3 이상 10,000 이하

- N개의 정수는 모두 1 이상 100,000 이하

- M은 N 이상 1,000,000,000 이하

 

과정

N과 M은 10억 이하기 때문에 데이터 타입은 int로 설정한다.

 

지방의 수 N이 10000이 주어지고 모든 예산이 100000이라도 10000 * 100000 = 10억 이기 때문에

총 예산을 담아놓는 공간의 데이터 타입은 int로 설정한다.

 

1. 예산을 받으면서 나올 수 있는 예산 상한의 한계치를 구한다.

for (int i = 0; i < N; i++)
	{
		cin >> budget[i];
		if (end < budget[i]) end = budget[i];
	}

예산 상한의 한계치를 구하는 이유는 예산 상한액에 대한 이분 탐색을 진행하기 때문이다.

 

2. 예산 상한액을 기준으로 이분 탐색을 진행하며 현재 상한액에서 나올 수 있는 최대 예산을 구한다.

for (int i = 0; i < N; i++)
		{
			if (budget[i] > mid)
			{
				sum += mid;
			}
			else
			{
				sum += budget[i];
			}
		}

탐색하고 있는 예산의 값이 현재 상한액보다 크다면 상한액만큼 값을 더해주고

상한액보다 작다면 기존 예산의 값만큼 더해준다.

 

ex) 예산 = {120, 110, 130, 140}, 상한액 = 120 -> 120 + 110 + 120 + 120

130과 140은 상한액보다 크기 때문에 상한액을 더해주고 120과 110은

상한액 이하기 때문에 기존 값을 더해준다.

 

3. 현재 예산 상한액으로 나올 수 있는 총 예산액을 기준으로 탐색을 진행한다.

if (sum <= M)
{
	start = mid + 1;
	ans = mid;
}
else
{
	end = mid - 1;
}

현재 예산 상한액으로 나올 수 있는 총 예산액이 기존에 정해진

총예산 M보다 작다면 예산 상한액을 늘려주고크다면 예산 상한액을 줄여준다. 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int budget[10001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, M, ans = 0;
	int start = 0;
	int end = 0;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> budget[i];
		if (end < budget[i]) end = budget[i];
	}

	cin >> M;

	while (start <= end)
	{
		int mid = (start + end) / 2;
		int sum = 0;

		for (int i = 0; i < N; i++)
		{
			if (budget[i] > mid)
			{
				sum += mid;
			}
			else
			{
				sum += budget[i];
			}
		}

		if (sum <= M)
		{
			start = mid + 1;
			ans = mid;
		}
		else
		{
			end = mid - 1;
		}
	}

	cout << ans;
}