2512번-예산

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

2512번: 예산

---

접근방법

https://hyeophyeop.tistory.com/2?category=1003847 와 유사한 문제 입니다.

문제 접근을 위한 시간복잡도 계산, 자료형 설정부터 이분 탐색을 위한 범위 지정까지 유사합니다.

차이점은 이분탐색을 시작하는 while문 안에서 기준값 mid를 활용하여 arr에 대한 값들의 비교 연산만 다릅니다.

 

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1e4 + 1;
 
ll arr[MAX];
int main(void)
{
    fastio;
 
    int n;
    cin >> n;
 
    ll ctValue;
    ll maxValue = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        maxValue = max(maxValue,arr[i]);
    }
    cin >> ctValue;
 
    ll left = 0;
    ll right = maxValue;
    ll mid = (left + right) / 2;
    ll ans = 0;
    while(left <= right)
    {
        mid = (left + right) / 2;
 
        ll sum = 0;
        for(int i = 0; i < n; i++)
            arr[i] > mid ? sum += mid : sum += arr[i];
 
        if(sum <= ctValue)
        {
            left = mid + 1;
            ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans << "\n";
}