[프로그래머스] 예산

링크

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스

풀이

정해진 예산의 총액 이하에서 가능한 최대의 총 예산을 구해야 한다.

 

처음 생각을 했을때는 총 예산/n 보다 작은 지방 예산을 총 예산에서 점점 빼 가며 최대의 예산을 구하면 되지 않을까 라고 생각을 하였지만, 시간복잡도에서 o(n^2)이 나올수 있을거 같아 다른 생각을 하다 이분탐색을 이용 하게 되었다.

 

이분 탐색은 left, right, mid 를 이용하여 o(log n)의 시간복잡도를 가지는 알고리즘 이며

밑의 코드에서 left, right, mid는 배정 가능한 예산을 저장하는 변수 이다.

left에는 나올수 있는 예산중 가장 작은 수인 1

right에는 나올수 있는 예산중 가장 큰 수(budgets을 정렬한 맨 끝 수)인 budgets.end()

mid는 (left + right)/2의 값

 

지방에서 요청한 금액이 상한액 미만의 금액이면 지방에서 요청한 금액을 그대로 예산의 합계에 더해주고

반대로 지방에서 요청한 금액이 상한액 이상이라면 상한액을 더해주고

 

이때 더해준 예산의 총 합이 국가의 예산보다 높으면 right를 mid-1 로 갱신하여 상한 금액을 줄여주고

반대로 예산이 작으면 left를 mid+1로 갱신하여 상한 금액을 높여 준다.

 

left를 갱신해 줄때 상한액은 점점 증가하고 있기때문에 answer를 mid로 저장해주면 최대값이 계속 갱신 된다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>

#define INF 1e9
#define SIZE 110000

using namespace std;

typedef long long int ll;

int solution(vector<int> budgets, int M) {
	sort(budgets.begin(), budgets.end());
	int left = 1 , right = budgets.back(), mid;
	int answer = 0;

	while (left <= right) {
		mid = (left + right) / 2;
		int sum = 0;
		for (auto b : budgets) {
			if (b <= mid) {
				sum += b;
			}
			else if (b > mid) {
				sum += mid;
			}
		}

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

	return answer;
}