백준 2512번 [예산](C++) -yes6686- 티스토리

백준 문제 풀이: 2512 (예산)

---

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

문제 설명:

각 지방에서 요청한 예산의 합이 국가 예산 총액을 초과할 경우, **상한선**을 정해 각 지방의 예산을 조정하는 문제입니다. 예산이 상한선 이하인 경우는 요청한 예산을 그대로 배정하고, 상한선을 초과하면 상한선만큼만 배정합니다. 상한선의 **최댓값**을 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[10001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 지방의 수
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }

    int m; // 총 예산
    cin >> m;

    sort(arr, arr + n); // 예산 요청을 정렬

    // 예산이 충분한 경우: 최대 요청값 출력
    if (sum <= m) {
        cout << arr[n - 1] << '\n';
        return 0;
    }

    // 이분 탐색을 사용한 상한선 찾기
    int s = 0, e = arr[n - 1], ans = 0;

    while (s <= e) {
        sum = 0;
        int mid = (s + e) / 2;

        // 상한선(mid)에 맞게 예산 합 계산
        for (int i = 0; i < n; i++) {
            if (arr[i] <= mid) {
                sum += arr[i];
            } else {
                sum += mid;
            }
        }

        // 총 예산 조건 검사
        if (sum > m) {
            e = mid - 1; // 상한선 낮추기
        } else {
            s = mid + 1; // 상한선 높이기
            ans = max(ans, mid); // 상한선 최댓값 갱신
        }
    }

    cout << ans;
}

---

코드 설명

• 입력 처리: - 예산 요청을 배열에 저장한 뒤, 전체 요청 예산의 합을 계산합니다.
• 예산 조건 확인: - 예산의 합이 총 예산보다 작거나 같은 경우, 가장 큰 예산 요청값이 상한선이 됩니다.
• 이분 탐색: - 상한선의 최댓값을 찾기 위해 이분 탐색을 진행합니다. - 중간값(mid)을 상한선으로 가정하고, 이를 기준으로 각 지방에 배정된 예산의 합을 구합니다.
• 조건 검사: - 합이 총 예산을 초과하면 상한선을 낮추고, - 합이 총 예산 이하이면 상한선을 높이며 최댓값을 갱신합니다.

---

시간 복잡도 분석

• 이분 탐색의 시간 복잡도는 **O(log(max(arr)))**입니다.
• 각 이분 탐색 단계에서 예산의 합을 계산하는 시간 복잡도는 **O(n)**입니다.
• 따라서 전체 시간 복잡도는 **O(n log(max(arr)))**입니다.

---

입출력 예시

• 입력 예시:

  4  
  120 110 140 150  
  485

• 출력 예시:

  127

---

결론

이 문제는 **이분 탐색**을 이용해 상한선을 찾아내는 문제입니다. 예산의 합이 주어진 총 예산을 초과하지 않도록 하면서 상한선을 최대한 높이는 방법을 구현합니다. 이분 탐색을 통해 효율적으로 답을 구할 수 있습니다.