문제 출처 : https://www.acmicpc.net/problem/2512

문제 정리

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

• 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

문제 해결 방법

처음엔 단순하게 수학 문제라고 생각해서 어떻게 풀지 30분 정도 끄적거렸다.

그러다가 순간적으로 0부터 완전탐색을 해야겠다는 아이디어가 떠올랐다.

하지만 범위가 상당히 커서 바로 이분탐색을 적용했다.

→ 이분탐색

코드

• click

코드 설명

1. mid 값을 구하고 전체 예산을 계산해서 만약 음수라면 mid 값이 작아져야한다.
   • 예산이 오버되서 부족하다는 의미다.
2. 양수라면 예산이 남는다는 의미라서 mid값이 커져야한다.