[ 백준 ] 2512 예산 - JavaScript

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

 

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

 

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

 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

 

입출력 예시

입력

4
120 110 140 150
485

 

출력

127

 

 

 

---

 

 

풀이

'use strict';
const fs = require('fs');

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = 'input.txt';

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split('\n');
const N = Number(input.shift());
const sortedList = input
  .shift()
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);
const maxBudget = Number(input.shift());
const div = Math.floor(maxBudget / N);

function binarySearch(sortedList, div) {
  const lowData = [];
  const highData = [];
  const start = 0;
  let end;
  let mid;

  while (sortedList.length !== 0) {
    end = sortedList.length - 1;
    mid = Math.floor((start + end) / 2);

    if (sortedList[mid] <= div) {
      lowData.push(...sortedList.splice(0, mid + 1));
    } else {
      highData.unshift(...sortedList.splice(mid, sortedList.length - mid));
    }
  }

  return [lowData, highData];
}

function solution(sortedList, maxBudget, div) {
  let lowData = [];
  let highData = [...sortedList];
  let remainBudget;
  let upperLimit = div;

  while (1) {
    const [low, high] = binarySearch([...highData], upperLimit);
    if (high.length === highData.length) break;

    lowData.push(...low);
    highData = [...high];

    if (lowData.length === 0) {
      remainBudget = maxBudget;
    } else {
      remainBudget = maxBudget - lowData.reduce((a, b) => a + b);
    }

    upperLimit = Math.floor(remainBudget / highData.length);
  }

  if (highData.length === 0) {
    return lowData[lowData.length - 1];
  } else {
    return upperLimit;
  }
}

console.log(solution(sortedList, maxBudget, div));

 

예를 들어, 요청 예산이 사진과 같을 때 총 국가 예산이 485라면, 지방은 4곳이니까 기준 상한액을 485 / 4 = 121 정도로 두고 시작할 수 있다.

 

기준 상한액을 이용한 이분 탐색

먼저 이분탐색을 이용해 상한액보다 작은 값들과 큰 값들로 나눈다.

• 작은 값들: 예산을 그대로 줄 수 있음 → 예산 초과 없음
• 큰 값들: 상한액으로 잘라야 함 → 조정 대상

작은 값은 조정 대산이 아니므로 고정이고, 큰 값들만 조정해야 하므로 작은 값들의 합을 국가 예산에서 미리 빼줘야 한다.

 

예시) 작은 값 [110, 120] → 합계 230  
485 - 230 = 255 (조정 가능한 예산)

 

이제 이 255를 남은 2개의 지방에 골고루 분배한다고 하면 새로운 상한액은 127(255 / 2 = 127)이 된다.

 

여기서 중요한 포인트

 

이분 탐색을 한 번만 하면 안 된다.

 

예를 들어 [1, 3, 5]라는 예산 요청과 총 예산이 8일 때를 생각해보자.

• 처음 상한액 = 8 / 3 = 2
• 작은 값: [1]
• 큰 값: [3, 5]
• 남은 예산 = 8 - 1 = 7
• 다시 상한액 = 7 / 2 = 3

이러면 3은 이미 예산 초과 없이 줄 수 있는 값이기 때문에 큰 배열이 아니라 작은 배열로 다시 분류되어야 한다.

 

✅ 그래서 어떻게 해야 할까?

 

상한액을 계산한 뒤, 그 상한액 이하인 값들은 무조건 작은 배열로 옮겨줘야 한다.

이 과정을 반복하면서 상한액을 계속 재조정해야 정확한 최적 상한액을 찾을 수 있다.

 

요약 정리

• 상한액을 기준으로 예산을 나눈다 (이분 탐색)
• 작은 값들은 예산 초과 걱정이 없으니 고정
• 큰 값들만 조정 대상으로 남겨두고 다시 상한액을 계산
• 상한액보다 작거나 같은 값은 반복적으로 작은 배열로 옮겨야 함
• 이 과정을 예산이 더 이상 나눠지지 않을 때까지 반복한다

최종 정답 조건

• 상한액보다 큰 예산이 더 이상 없다 → 가장 큰 요청 금액을 그대로 줄 수 있으므로 그것이 정답
• 상한액보다 큰 예산이 남아 있다 → 그 상한액을 넘기지 않도록 잘라주는 것이 정답 (상한액 출력)