BOJ - 2512 예산

문제 링크 : https://www.acmicpc.net/problem/2512

문제 티어 : 실버2

문제 유형 : 이진 탐색

문제 풀이
 한정된 값을 최대한의 예산으로 나누어 주어야 한다.

1) 적절한 상한금액을 찾는 것이 목표
2) 배정을 다하고도 남는 예산이 0이상이어야함

3) 남은 예산이 0에 가까워야 함

 

이진 탐색 방법으로 생각하면 양 쪽 끝을 기준으로 최댓값과 최솟값을 잡고 그 사이를 점점 간격을 좁혀 나가면서 예산의 최댓값을 찾아주는 것이 핵심이다. 예를 들면 아래와 같다. 

1) 최솟값 = 0 , 최댓값 = Math.max()  , mid = (최솟값 + 최댓값 ) / 2

2) 만약 배정된 예산의 총합이 mid 보다 크면 상한액을 줄여야 하므로 mid를 -1 해서 점점 줄임

3) 만약 배정된 예산의 총합이 mid 보다 작거나 같으면 상한액을 높여도 되므로 상한액 범위를 올린다.

 

위 풀이를 코드로 표현하면 아래와 같다.

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

// 이진 탐색 분류
let start = 1; // 시작점
let end = arr.reduce((a,b) => Math.max(a,b)); // 최댓값 끝 점
let result = 0; // 결괏값을 담을 변수

while(start<=end){
    let mid = parseInt((start+end)/2);
    let total = 0; // 배정된 예산 총액
    // arr 순회해서 예산 모두 더해줌
    for(x of arr) {
        total+=Math.min(mid,x); // 만약 mid가 더 작으면 mid 그게 아니면 x를 total에 반영
    }
    // 만약 총액이 배정된 예산보다 적은 경우
    if(total<=M) {
        result = mid;
        start = mid+1;
    } else {
        end = mid - 1;
        }
 }
 console.log(result);

 

시간복잡도 : 입력처리 : O(N) + 이진탐색 부분 : while -> O(log M) , for 루프 -> O(N) => O(NlogM)