백준 2512: 예산 - javascript (이진탐색)

문제 출처 

https://www.acmicpc.net/problem/2512

2512번: 예산

문제

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

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 이하이다. 

출력

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

예제 입력 1 복사

4
120 110 140 150
485

예제 출력 1 복사

127

예제 입력 2 복사

5
70 80 30 40 100
450

예제 출력 2 복사

100

문제 풀이 힌트 

이진탐색을 활용했다. 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input[0]); //지방 수 
const budgets = input[1].split(' ').map(Number); //요청 예산들
const M = Number(input[2]); //총 에산 

const answer = getMaxBudget(N, budgets, M);

function getMaxBudget(N, budgets, M) {
   let min = 1; //최소상한액
   let max = Math.max(...budgets); //최대상한액 
    
   while(min <= max){
       const mid = Math.floor((min + max)/2); //temp 상한액  
       let total = 0; //temp 상한액에 따른 총 예산 
       
       //정한 상한액에 따라 총 예산 계산하는 반복문
       for(let i=0; i<N; i++){
           if(budgets[i] > mid){ //상한액보다 요청한 예산이 더 클 때 
               total += mid; //상한액만큼 total에 추가 
           }else { //상한액보다 요청한 예산이 작거나 같을 때 
               total += budgets[i] //요청한 예산만큼 total에 추가 
           }
       }
       
   
       if(total <= M){ // temp 상한액에 따른 총 예산이 주어진 총예산보다 작거나 같을 때 
           min = mid + 1;  
       }else { // temp 상한액에 따른 총 예산이 주어진 총예산보다 작을 때 
           max = mid-1;
       }
   }
    return max //min과 max사이 모든 값에서 최대 값을 상한액으로 설정 ! 
}

console.log(answer);

Only 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input[0]);
const budgets = input[1].split(' ').map(Number);
const M = Number(input[2]);

const answer = getMaxBudget(N, budgets, M);

function getMaxBudget(N, budgets, M) {
   let min = 1; 
   let max = Math.max(...budgets); 
    
   while(min <= max){
       const mid = Math.floor((min + max)/2); 
       let total = 0; 
       
       for(let i=0; i<N; i++){
           if(budgets[i] > mid){
               total += mid; 
           }else {
               total += budgets[i]
           }
       }
       
       if(total <= M){
           min = mid + 1; 
       }else {
           max = mid-1;
       }
   }
    return max
}

console.log(answer);

 

알고가는 ppoint 

01. 시간 복잡도 O(log N) , 일반적인 입력 범위에서 상당히 효율적으로 동작 (대개 10,000 이하의 크기를 갖는 입력)

02. 내 틀린 풀이 코드 ) 아직도 왜 틀렸는지 못찾아냄 //밑에 내 코드가 왜 런타임 에러가 뜨는지 나온다. 알고가기 ) 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const N = Number(input.shift()); 
let req = input[0].split(' ').map(v => +v); 
const M = Number(input[1]); 

req.sort((a,b) => a-b); 

let start = 1; 
let end = Math.max(...req); 
let answer = binarySearch(start, end, M); 

function binarySearch(start, end, M){
  let mid = 0; 
  if(start > end) return mid; 
  mid = Math.floor((start+end)/2);
   
   let limit  = count(mid); 
   if(M < limit){
       return binarySearch(mid+1, end, M)
   }else {
       return binarySearch(start, mid-1, M)
   }
}

//계산해주는거 
function count(num){
    let answer = 0; 
    for(let i=0; i<N; i++){
        if(num - req[i] >=0){
            answer += req[i]
        }else {
            answer += (req[i]- num)
        }
    }
    return answer; 
}

console.log(answer); 

//런타임 에러 발생 이유 
//01.count[mid] 이런식으로 씀 
//02. mid를 선언하기 전에 return mid 이런식으로 씀 
//03. const req 로 선언했으면서 sort로 정렬할 때 재할당 했음.