[C++] 백준 2512 예산

 

문제 설명

 이 문제는 이분탐색, 매개 변수 탐색 문제 중에서 쉬운 편이라고 생각했다. (비록 여러 번 틀렸지만..^^)

 

문제 설명 그대로 정해진 총액 M이하에서 가능한 최대의 총 예산을 배정하는 문제이다.

배정될 수 있는 경우엔 요청 금액을 그대로 배정하고, 그렇지 않은 경우엔 상한선을 배정한다.

 

findLimit함수를 통해서 현재 정한 상한선(money)을 기준으로 M만큼 줄 수 있는 지 확인했다.

result를 통해서 findLimit에서 참인 경우 해당 돈을 저장했다.

 

틀렸던 이유: left값을 처음에 입력받은 예산들 중 가장 작은 값을 넣어서 틀렸다.

 

#include<stdio.h>
#include<algorithm>

using namespace std;

int N, M;
int city[10004];

bool findLimit(int money){
	int sum=0;
	
	for(int i=0;i<N;i++){
		sum+=min(money, city[i]);
	} 
	
	return sum<=M; 
}

int main(){
	
	int i, left=1,right=0, mid=0, result=0;
	
	scanf("%d",&N);
	
	for(i=0;i<N;i++){
		scanf("%d",&city[i]);
		right=max(right,city[i]);
		
	}
	scanf("%d",&M);
	
	while(left<=right){
		
		 mid=(left+right)/2;
		
		if(findLimit(mid)){
			left=mid+1;
			result=mid;
		}else
			right=mid-1;
	}
	
	printf("%d",result);
	
	return 0;
}