백준 2512 예산 C++,

백준 예산 2512 C++

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

• 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
• 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

테스트케이스

예제 입력 1

4
120 110 140 150
485

예제 출력 1

127

예제 입력 2

5
70 80 30 40 100
450

예제 출력 2

100

---

문제 설명

문제 배경

국가는 한정된 총 예산을 가지고 여러 지방에서 요청하는 예산을 심사합니다. 각 지방은 자신들이 필요한 금액을 요청하지만, 총 예산이 정해져 있기 때문에 모든 요청을 그대로 들어줄 수 없는 경우가 생깁니다. 따라서 "상한액"이라는 개념을 도입하여 예산을 공정하게 분배합니다.

---

예산 배정 규칙

1. 모든 요청 합이 총 예산 이하라면
   → 각 지방이 요청한 금액을 그대로 배정합니다.
   → 이 경우 출력은 단순히 요청된 금액 중 최댓값입니다.
2. 모든 요청 합이 총 예산을 초과한다면
   → 일정한 정수 상한액(cap)을 정합니다.
   → 요청 금액이 상한액보다 크면 상한액만 배정합니다.
   → 요청 금액이 상한액보다 작거나 같으면 그대로 배정합니다.
   → 이때, 배정된 예산들의 합이 총 예산 이하가 되면서 최대가 되도록 상한액을 찾아야 합니다.

---

문제의 목표

주어진 요청 금액들과 총 예산이 있을 때, 위 조건을 만족하는 배정된 예산 중 최댓값(상한액)을 구하는 것입니다.

---

예시로 이해하기

예제 1

입력:

4
120 110 140 150
485

• 요청 합 = 120+110+140+150 = 520
• 총 예산 = 485
• 520 > 485 이므로 상한액을 정해야 합니다.

만약 상한액 = 127로 정하면:

• 120 → 120
• 110 → 110
• 140 → 127
• 150 → 127

합계 = 484
→ 총액 485 이하에서 가장 큰 합, 따라서 정답은 127입니다.

예제 2

입력:

5
70 80 30 40 100
450

• 요청 합 = 320
• 총 예산 = 450
• 320 ≤ 450 → 요청 금액 그대로 배정 가능.

→ 따라서 최댓값 = 100이 답입니다.

---

핵심 포인트

• 이 문제는 상한액을 어떻게 정하느냐가 관건입니다.
• 상한액을 하나 정했을 때, 그 합계는 상한액에 따라 증가하거나 감소하는 단조성을 보입니다.
• 따라서 이분 탐색을 활용하여 상한액을 찾아내는 것이 효율적입니다.

---

문제풀이

• 지방 예산 요청: [120, 110, 140, 150]
• 총 예산: 485

총 요청 합계는 520입니다. 총액 485를 초과하므로, 모든 요청을 그대로 줄 수는 없습니다. 따라서 상한액을 찾아야 합니다.

---

탐색 범위 설정

상한액은 0 이상, 최대 요청액 150 이하입니다.
따라서 처음 탐색 구간은 다음과 같습니다.

0, 1, 2, ..., 149, 150

즉, low = 0, high = 150에서 시작합니다.

---

1단계: 첫 mid 계산

mid = (0 + 150) / 2 = 75
이제 상한액을 75라고 가정하고 배정 금액 합계를 계산합니다.

• 요청 120 → 75
• 요청 110 → 75
• 요청 140 → 75
• 요청 150 → 75

총합 = 300
→ 총합(300) < M(485) 이므로 아직 예산을 더 줄 수 있습니다.
즉, 상한액을 더 키워도 괜찮습니다. 따라서 탐색 범위를 오른쪽으로 이동합니다.
새로운 탐색 구간:

75, 76, ..., 149, 150

→ 기록: ans = 75 (일단 가능한 값으로 저장)

---

2단계: mid 재계산

mid = (76 + 150) / 2 = 113
상한액 = 113으로 가정하고 합계 계산:

• 120 → 113
• 110 → 110
• 140 → 113
• 150 → 113

총합 = 449
→ 총합(449) < M(485) → 여전히 더 키울 수 있습니다.
탐색 범위를 오른쪽으로 이동합니다.
새 구간:

114, 115, ..., 149, 150

→ 기록: ans = 113

---

3단계: mid = 132

mid = (114 + 150) / 2 = 132
상한액 = 132로 계산:

• 120 → 120
• 110 → 110
• 140 → 132
• 150 → 132

총합 = 494
→ 총합(494) > M(485) → 예산을 초과했습니다.
따라서 상한액을 줄여야 합니다.
탐색 범위를 왼쪽으로 이동합니다.
새 구간:

114, 115, ..., 131

→ 기록: ans는 갱신하지 않음 (초과했으므로 저장 불가)

---

4단계: mid = 122

mid = (114 + 131) / 2 = 122
상한액 = 122:

• 120 → 120
• 110 → 110
• 140 → 122
• 150 → 122

총합 = 474
→ 총합(474) < 485 → 가능
탐색 범위를 오른쪽으로 이동합니다.
새 구간:

123, 124, ..., 131

→ 기록: ans = 122

---

5단계: mid = 127

mid = (123 + 131) / 2 = 127
상한액 = 127:

• 120 → 120
• 110 → 110
• 140 → 127
• 150 → 127

총합 = 484
→ 총합(484) ≤ 485 → 가능
탐색 범위를 오른쪽으로 이동합니다.
새 구간:

128, 129, 130, 131

→ 기록: ans = 127

---

6단계: mid = 129

mid = (128 + 131) / 2 = 129
상한액 = 129:

• 120 → 120
• 110 → 110
• 140 → 129
• 150 → 129

총합 = 488
→ 총합(488) > 485 → 초과
탐색 범위를 왼쪽으로 이동합니다.
새 구간:

128

→ ans는 갱신하지 않음

---

7단계: mid = 128

mid = 128일 때:

• 120 → 120
• 110 → 110
• 140 → 128
• 150 → 128

총합 = 486
→ 총합(486) > 485 → 초과
탐색 범위를 왼쪽으로 이동 → high = 127
탐색 종료.

---

최종 결과

탐색이 끝나면 ans = 127이 남습니다.
따라서 출력은 127입니다.

---

정리

이 과정을 표로 요약하면 다음과 같습니다.

단계	low	high	mid	합계	M와 비교	탐색 방향	ans
1	0	150	75	300	< M	오른쪽	75
2	76	150	113	449	< M	오른쪽	113
3	114	150	132	494	> M	왼쪽	113
4	114	131	122	474	< M	오른쪽	122
5	123	131	127	484	< M	오른쪽	127
6	128	131	129	488	> M	왼쪽	127
7	128	128	128	486	> M	왼쪽	127

---

전체 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void)
{
    int N, sumN = 0, budget, ans = 0;
    cin >> N;
    int* arr = new int[N];
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        sumN += arr[i];
    }
    cin >> budget;
    if (sumN <= budget)
    {
        cout << *max_element(arr, arr + N) << endl;
        return 0;
    }
    sort(arr, arr + N);
    int left = 0;
    int right = *max_element(arr, arr + N);
    while (left <= right)
    {
        int mid = (left + right) / 2;
        sumN = 0;
        for (int i = 0; i < N; i++)
        {
            if (arr[i] <= mid)
                sumN += arr[i];
            else
                sumN += mid;
        }
        if (sumN == budget)
        {
            cout << mid << endl;
            return 0;
        }
        if (sumN < budget)
        {
            left = mid + 1;
            ans = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
    cout << ans << endl;
    delete[] arr;
}

---

개별 코드 설명

1. 입력 및 초기화

int N, sumN = 0, budget, ans = 0;
cin >> N;
int* arr = new int[N];
for (int i = 0; i < N; i++)
{
    cin >> arr[i];
    sumN += arr[i];
}
cin >> budget;

• N: 지방의 수
• arr: 각 지방이 요청한 예산 배열
• sumN: 전체 요청 예산 합계
• budget: 총 예산 M
• ans: 최종 답 저장

→ 이 단계에서 모든 요청을 입력받고 총합을 구합니다.

---

2. 전체 요청이 예산 이하인 경우

if (sumN <= budget)
{
    cout << *max_element(arr, arr + N) << endl;
    return 0;
}

• 만약 모든 요청의 합이 총 예산보다 작거나 같다면, 그대로 다 줄 수 있습니다.
• 이 경우 출력은 단순히 요청들 중 최댓값입니다.

---

3. 탐색 범위 설정

sort(arr, arr + N);
int left = 0;
int right = *max_element(arr, arr + N);

• 상한액을 정하기 위해 이분 탐색 범위를 설정합니다.
• left = 0, right = 최대 요청값.

---

4. 이분 탐색 실행

while (left <= right)
{
    int mid = (left + right) / 2;
    sumN = 0;
    for (int i = 0; i < N; i++)
    {
        if (arr[i] <= mid)
            sumN += arr[i];
        else
            sumN += mid;
    }

• mid를 상한액 후보로 가정.
• 요청 배열을 순회하면서 min(arr[i], mid) 값을 모두 합산.
• 이렇게 계산된 sumN이 총 예산과 어떻게 비교되는지 확인합니다.

---

5. 조건에 따른 분기

if (sumN == budget)
{
    cout << mid << endl;
    return 0;
}

• 만약 정확히 예산과 일치하면 바로 출력하고 종료.

if (sumN < budget)
{
    left = mid + 1;
    ans = mid;
}
else
{
    right = mid - 1;
}

• sumN < budget이면 예산을 더 줄 수 있으므로 상한액을 더 크게 잡음 (left = mid + 1).
• sumN > budget이면 예산을 초과했으므로 상한액을 줄여야 함 (right = mid - 1).
• 가능한 답을 갱신할 때는 ans = mid.

---

6. 최종 출력

cout << ans << endl;
delete[] arr;

• 탐색이 끝나면 저장된 ans를 출력.
• 동적 할당한 배열은 해제.

---

결론

• 이 문제는 상한액과 배정 예산 총합 사이의 단조성을 이용해 푸는 전형적인 이분 탐색(파라메트릭 서치) 문제입니다.
• 단순 합이 예산을 초과하지 않으면 최대 요청값을 출력, 초과한다면 이분 탐색으로 상한값을 찾습니다.
• 시간 복잡도는 O(N log(max(arr))). N=10,000, max=100,000에서도 충분히 빠릅니다.

즉, 핵심은 mid를 상한액으로 가정하고 합계를 계산하며, 조건에 따라 탐색 범위를 줄여나가는 과정입니다.