[ 백준 2512 ] 예산 (C++) - 이분탐색

---

🔗 문제 링크

2512번: 예산

---

💡 문제 풀이 및 해석

처음에는 평균을 잡아놓고, 평균 아래의 가격과의 차액을 더하는 방식으로 할려 했지만, 차액을 더하는 도중에 평균보다 위였던 금액이 평균보다 낮아져 버릴 수도 있음을 알았다. 그래서 차라리 이분탐색으로 금액을 정해놓고 이 금액이 가능한지 판별하는 방식으로 접근하기로 했다.

1. 만약 전체 금액 <= 예산 인 경우 전체 금액을 모두 준다.
2. 이분탐색으로 지불할 최대 예산을 정한다.
3. 예산이 가능한지 판단하는 방식은 전부 더하는 방식으로 한다.
   3-1. 예산 <= 평균 인 경우는 예산을 더해준다.
   3-2. 예산 < 평균 인 경우는 평균을 더해준다.
4. 결과를 출력한다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>

using namespace std;

int N, maxCost;
int sum = 0;
int Max = 0;
vector<int> country;

void input() {
    cin >> N;
    country = vector<int>(N);

    for (int i = 0; i < N; i++) {
        cin >> country[i];
        sum += country[i];
        Max = max(Max, country[i]);
    }
    cin >> maxCost;
}

bool isCan(int mid) {
    int cost = 0;
    for (int cash : country) {
        if (cash <= mid) cost += cash;
        else cost += mid;
    }
    if (cost <= maxCost) return true;
    else return false;
}

/*
int sol() {
    int left = 0, right = maxCost;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (isCan(mid)) left = mid + 1;
        else right = mid - 1;
    }
    return right;
}
*/

int sol() {
    int left = 0, right = maxCost;
    while (left < right) {
        int mid = (left + right) / 2;
        if (isCan(mid)) left = mid + 1;
        else right = mid;
    }
    return left - 1;
}

int main() {

    input();
    if (sum <= maxCost) {
        cout << Max;
        return 0;
    }
    cout << sol();

    return 0;
}

---

🤔 문제 후기

처음부터 단위가 큰 것을 보고 이분탐색을 생각했어야 했는데, 일단 그리디한 방식으로 접근을 했었다. 이런저런 생각을 하다가 결국 이분탐색으로 접근을 했는데, 개인적으로 주석친 부분처럼 right를 반환하면서 풀어왔는데 이번에는 어쩌다보니? left - 1을 return 하게 되었다... 나중에 이분탐색에 대해서도 더 공부를 해야겠다고 생각했다.