9. 2581 : 예산

문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1842&sca=50&sfl=wr_subject&stx=%EC%98%88%EC%82%B0&sop=and

JUNGOL | 예산 > 문제은행

문제 풀이 :

#include <stdio.h>

int N, M;
int arr[10001];//지방의 최대 수
int sum_don = 0;
int solve(int m) {
	//도시별 상한가 이하이면 그대로 배정하고
	//아니면 상한가로 배정하여
	//N개의 도시의 예산 합계를 리턴
	sum_don = 0;
	for (int i = 0; i < N; i++) {
		if (arr[i] <= m) {
			//상한가를 넘으면 상한가를 넣어준다.
			sum_don += arr[i];
		}
		else {
			sum_don += m;

		}
	}
	//상한가를 넘지 않는 도시 예산의 총합
//  printf("%d\n", sum_don);
	return sum_don;
}
int main() {
	int i, m, s = 0, e = 0, sol = 0;
	scanf("%d", &N);    //지방의 수
	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
		if (e < arr[i]) e = arr[i];  //예산액중 max값
	}
	scanf("%d", &M);

	while (s <= e) {
		m = (s + e) / 2;    //상한가를 mid로 계산

		if (solve(m) <= M) {
			//총액 이내에 만족한다면 예산액을 늘려본다
			sol = m;
			s = m + 1;
		}
		else {
			//총액을 초과하면 예산액을 줄여본다.
			e = m - 1;
		}
	}
	printf("%d\n", sol);
	return 0;
}

 

이진탐색의 범위를 정하고 (s는 0 e는 예산액 중 MAX값) 총액에 만족할 때 까지 mid 값을 이진탐색 한다. 이 때 주의 해야 할 점은 문제에 따라 예산의 합계가 정수 범위를 넘어 갈 수 있기 때문에 문제 조건을 잘 보고 int로 선언할 지 long long int로 선언할지 정해야 한다.