2512번: 예산

문제 접근 🤔

• 전체 국가 예산의 한도 내에서 줄 수 있는 예산의 상한액을 구하는 문제.
• 이분 탐색을 하기 전에 예외의 경우를 살펴보자.
• 총 예산의 한도 값보다 예산 요청 리스트의 최솟값에 n을 곱한 값이 크거나 같을 때는, 이분 탐색을 진행할 필요 없이 상한액은 한도를 n으로 나눈 몫이다. ex) 예산 요청: 2, 2, 3 and 한도: 5 → 상한액: 1
• 이러한 경우를 제외하고서는 상한액은 예산 요청 리스트의 최솟값과 최댓값 사이에 있을 것이다.
• 효율적으로 찾기 위해 이분 탐색을 진행하며 상한액의 최댓값을 찾아보자.
• 범위의 중간값을 상한액으로 지정했을 때 요청 예산이 더 크다면 예산을 상한액만큼 지급하고, 같거나 작다면 요청 예산만큼 지급한다.
• 이 값들을 더한 예산의 총합과 예산의 한도를 비교하여 이분 탐색을 진행하면 된다.
  
  
  

놓쳤던 부분 😅

• 없음
  
  
  

코드 😁

파이썬 코드(64 ms)

n, budgets, limit = int(input()), list(map(int, input().split())), int(input())
low, high = min(budgets), max(budgets)
maxBudget = 0

if limit <= low * n:
    maxBudget = limit // n
else:
    while low <= high:
        mid = (low + high) // 2
        
        budSum = 0
        for bud in budgets:
            budSum += mid if mid < bud else bud
        
        if budSum <= limit:
            maxBudget = max(maxBudget, mid)
            low = mid + 1
        else:
            high = mid - 1

print(maxBudget)

자바스크립트 코드(176 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [N, datas, M] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = (n, budgets, limit) => {
  let [low, high] = [Math.min(...budgets), Math.max(...budgets)];
  let maxBudget = Number.MIN_SAFE_INTEGER;

  if (limit <= low * n) {
    maxBudget = Math.floor(limit / n);
  } else {
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      let budSum = budgets.reduce((sum, bud) => (mid < bud ? sum + mid : sum + bud), 0);

      if (budSum <= limit) {
        maxBudget = Math.max(maxBudget, mid);
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  console.log(maxBudget);
};

solution(Number(N), datas.split(' ').map(Number), Number(M));