백준 2512번 예산 C++

 

 

1. 문제 풀이

국가의 예산을 분배하려고 한다.

각 부서에서의 모든 요청이 배정될 수 있다면 요청한 금액 그대로 배정하고

그렇게 되지 않는다면 특정한 정수 상한액을 계산하여 그만큼만 배정하고

상한액 이하면 요청한 금액으로 준다.

 

예를 들어 전체 예산이 458라고 하고

120, 110, 140, 150의 요청이 들어왔을때, 상한액을 127로 잡아준다.

그러면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하게 되고 그 합은 484로 최대치가 된다

모든 부서에 최대한 줄 수 있는 상한액을 설정하는 문제이다.

 

이분 탐색 활용하는 문제.