← 12주차 · 체크포인트 2
보통이분 탐색파라메트릭 서치

예산 배정

지방들의 예산 요청 금액 배열 budgets와 나라의 총예산 total이 주어져요. 각 요청에 상한액을 정해서, 요청 금액이 상한액보다 크면 상한액만큼만, 작거나 같으면 요청한 만큼 배정해요.

배정한 금액의 합이 total을 넘지 않는 선에서 상한액을 가능한 한 크게 정하려고 해요. 그 최대 상한액을 반환해요.

단, 모든 요청을 그대로 다 배정해도 total 이하라면, 상한액을 둘 필요가 없으니 요청 중 가장 큰 값을 반환해요.

예시

예시 1
입력
budgets = [120, 110, 140, 150], total = 485
출력
127
설명
상한액 127이면 120·110·127·127 = 484 ≤ 485예요. 128이면 486이 되어 넘쳐요.
예시 2
입력
budgets = [70, 80, 30], total = 200
출력
80
설명
다 합쳐도 180 ≤ 200이라 상한액이 필요 없어요. 가장 큰 요청 80을 반환해요.

제한 사항

  • 1 ≤ budgets.length ≤ 10,000
  • 1 ≤ budgets[i] ≤ 100,000
  • 1 ≤ total ≤ 1,000,000,000
상한액 후보를 [0, max(budgets)] 범위에서 이분 탐색해요. 어떤 상한액 x에서 배정액은 각 요청과 x 중 작은 값의 합이에요. 이 합이 total 이하면 더 크게(lo = mid + 1), 넘치면 더 작게(hi = mid - 1) 조절해요. 요청 총합이 total 이하인 경우만 따로 처리하면 돼요.
javascript
function budgetAllocation(budgets, total) {
  const sumAll = budgets.reduce((a, b) => a + b, 0);
  if (sumAll <= total) return Math.max(...budgets);
  let lo = 0;
  let hi = Math.max(...budgets);
  let best = 0;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    let used = 0;
    for (const b of budgets) used += Math.min(b, mid);
    if (used <= total) {
      best = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return best;
}
이전 문제체육복 나눠주기
다음 문제재귀 피보나치와 메모이제이션
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.