[2512] 예산, c++

[2512] 예산

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

2512번: 예산

한줄 후기 : 내 예산은 마이너스

#include <iostream>
#include <algorithm>
using namespace std;
int arr[10000];
int n, m;
bool check(int x){
	int cnt=0;
	for(int i=0; i<n; i++){
		if(arr[i] > x){
			cnt+=x;
		}
		else{
			cnt+=arr[i];
		}
	}
	if(cnt <= m)	return true;
	else	return false;
}
int main(){
	int l,r,ans=0, x;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	scanf("%d", &m);
	sort(arr,arr+n);
	l = 1;
	r = arr[n-1];
	while(l <= r){
		x = (l+r)/2;
		if(check(x)){
			l = x+1;
			ans = max(ans, x);
		}
		else{
			r = x-1;
		}
	}
	printf("%d", ans);
	return 0;
}

다른 이분 탐색 문제들 보다는 쉬웠던 것 같다. 예산 상한액을 정해놓고 넘지 않도록 상한액 보다 큰 예산은 무조건 상한액으로 줄이고, 그보다 작은 예산은 지원한다고 가정해서 가장 예산에 가깝도록 배정하는 금액을 찾아야 하는 문제이다. 이 문제는 딱 이분탐색 기준을 상한액으로 두면 될 것 같아서 쉬웠음.

left = 1, right 는 받은 예산의 가장 큰 값으로 두고 이분탐색을 한다. check 함수에서는 현재의 mid 값보다 큰 예산을 모두 mid 값으로 줄이고, 작은 예산은 그대로 둔 다음 합계를 계산하여 총 사용 가능 예산 보다 작으면 true, 크면 false 를 반환해 주면 된다.

나머지는 이분 탐색 하는 방식으로~