백준, BOJ, 2512번, 예산 C++ [CPP] ★★

이분탐색 중에서 풀만한 문제다.

조건을 빼먹으면 틀리는 문제..

그래서 나도 틀림..ㅋㅋㅋ

 

 

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

 

 

---

 

#맞는 풀이

#include <bits/stdc++.h>

using namespace std;

int N;
vector<long long> countryBudget;
long long total;
long long answer;
long long M;

//1.budget은 주어진 예산을 초과해서 분배해서는 안된다.
//2. budget은 상한만큼만 배정되어야 한다.
bool AssignBudget(long long budget){
    
    if(budget >M)return false; //1
    
    long long sum = 0;
    
    for(auto x : countryBudget){
        long long now = min(x, budget); //2
        sum += now;
    }
    
    if(sum <= total){return true;}
    else{return false;}
}

long long Search(long long left, long long right){
    long long mid = (left + right) / 2;

    if(left <= right){
        if(AssignBudget(mid)){
            answer = max(answer, mid); //해당 값 갱신
            return Search(mid+1, right);
        }else{
            return Search(left, mid-1);
        }
    }
    return left;
    
}




int main(){
    //1. 입력
    cin >> N;
    for(int i = 0; i<N; i++){
        long long x;
        cin >> x;
        countryBudget.push_back(x);
        M = max(M,x);
    }
    cin >> total;
    
    //2. 연산
    Search(0, total);
    
    
    cout << answer;
    
    return 0;
}

 

왜 이분탐색을 써야하느냐??

어떠한 숫자를 고르는 것인데 그 범위가 말도 안되니까?

즉, 0~xxxxx까지의 숫자 중 최댓값을 고르시오라는 문제가 나왔는데 범위가 엄청 크다??

-> N이 정말 크다?? 검색 시간을 줄일 방법을 찾아야 한다

-> 과연 결정 범위가 숫자 범위랑 어떤 관계를 가지고 있냐?

-> 음.. 딱 어느 범위 이상이면 false, 그 안이면 true 문제구나..?

-> 이분탐색을 쓸 수 있겠구나