2512 예산

n개의 예산신청들을 m 원으로 분배한다고 할 때, 다음과 같은 방법으로 분배한다고 한다.

  (1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

  (2) 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

이런 방법으로 분배할 때, 예산신청 이하의 수 중 최대의 상한액을 정하는 문제이다.

나에게 있어 상당히 암을 유발하는 문제였다.
각설하고 문제를 푼 방법은
우선 받아온 예산들을 오름차순으로 정렬 하고, 처음부터 점점 누적해가면서 끊을 곳을 정한다.
그리고  m * 끊은대까지 누적한 수 / 남은예산수 가 정답이 된다.
만약 끊어지지 못하면 가장 큰 예산을 출력하면 된다.

문제는 끊어주는 부분인데, 이는 누적한 수 + 그 바로 다음수 * 남은예산수 > m  를 만족 할 때 끊어주면된다.

소스