[프로그래머스 이분탐색] 예산 - C++

문제 출처입니다.

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산

구하고자 하는 건 한 지방의 예산 상한액이고, 이 예산의 범위가 1이상 100,000이하인 걸 보면

for문을 돌려 일일이 계산하는 방식이 아니라는 걸 알 수 있습니다.

 

따라서 효율을 위해 이분탐색을 합니다. 이분탐색 문제는 유형이 거의 비슷해요.

구하고자 하는 것의 범위를 알 때, 이분탐색을 통해 그 값 중 가장 적절한 값이 뭔지 찾는 겁니다.

말 그대로 원하는 값을 찾는 것, '탐색'하는 겁니다.

 

설명

 

이 문제에서 구하고자 하는 건 상한액이에요. 결국 한 지방이 가져가는 예산에 관한 값입니다.  

따라서 범위는 각 지방에서 요청하는 예산의 범위인 1이상 100,000이하입니다.

이 범위 내에서 mid값을 조정하면서 이분탐색을 진행하면 됩니다.

 

예산을 다 합쳐도 총 예산 이내라면 상한액을 둘 필요가 없습니다. 예산대로 모든 지방에게 줄 수 있으니까요.

이럴 땐 그냥 각 지방의 예산 중 최댓값을 상한으로 두어 바로 리턴하면 됩니다.

 

하지만 예산을 합칠 때 총 예산을 넘기는 경우는 모든 지방에 제대로 예산을 줄 수 없으니 상한액을 계산해야 합니다.

범위 내에서 조건을 맞추는 상한액을 이분탐색으로 찾습니다.

여기서의 조건은, 상한액을 적용하여 예산을 합칠 때 그 값이 총 예산 이내여야 만족하는 겁니다.

 

mid를 가지고 이분탐색을 해서 효율적으로, 빠르게 상한액을 찾는 문제였습니다.

#include <string>
#include <vector>
using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0;
    long long sum=0;
    int result = budgets[0];
    for(int i=0; i<budgets.size();i++){
        sum+=budgets[i];
        result = max(result,budgets[i]);
    }
    
    if(sum <= M){
        answer = result;
        return answer;
    }
  
    int left = 1;
    int right = 100000;
        
    while(left <=right){
        sum=0;
        int mid = (left+right)/2; //상한액 후보
        for(int i=0; i<budgets.size();i++){
            if(budgets[i]<mid)
                sum+=budgets[i];
            else
                sum+=mid;
        }
            
        if(sum >M) right = mid-1;
        else left = mid+1;
    }
    answer = right;
    return answer;

}