예산

예산

문제 설명

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

가능한 한 최대의

총 예산을 다음과 같은 방법으로 배정한다.

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

모든 요청이 배정될 수 없는 경우에는 특정한

정수

상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

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

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

예제 입력

4
120 110 140 150
485

예제 출력

127

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  const N = Number(input[0]);
  const arr = input[1].split(" ").map(Number);
  const limit = Number(input[2]);
  let result = 0;
  const size = arr.length - 1;

  arr.sort((a, b) => a - b);
  // 만약 기본 배열의 전체 합이 limit 보다 작으면 최댓 값 출력
  if (arr.reduce((a, b) => a + b) <= limit) result = arr[size];

  const bis = () => {
    let left = 1;
    let right = arr[size];
    let answer = 0;

    // 이분 탐색 진행
    while (left <= right) {
      let sm = 0;
      let mid = Math.floor((right + left) / 2);

      for (let num of arr) {
        // 배열의 원소 값이 mid 보다 크다면
        if (num > mid) {
          // 누적합에 mid 추가
          sm += mid;
        } else {
          // 아니라면 num 추가
          sm += num;
        }
      }
      // 전체 합산이 limit 보다 작으면
      if (sm <= limit) {
        // 결과 값 재할당
        answer = mid;
        // 더 가능한 경우 탐색
        left = mid + 1;
      } else {
        // 아니라면 줄이기
        right = mid - 1;
      }
    }
    return answer;
  };

  result = bis();
  console.log(result);
};
solution(input);

아이디어 / 접근법

1. 기본적인 이분탐색 문제로 접근
2. 원소의 값이 mid 보다 크다면 누적합에 mid 누적 아니라면 원소 값 누적
3. 누적합이 limit 보다 작다면 결과 재할당하고 범위 늘려서 탐색
4. 아니라면 right 값 줄여서 탐색

후기

이거는 되게 금방 풀었음 생각한 그대로 답이 나와서 쉬웠음 굿