[BOJ/C++] 예산(2512번)

1. 개요

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

2512번: 예산

1-1. 설명

국가는 정해진 예산 내에 최대한의 예산을 지방에 배정해주려고 한다. 각 조건에 맞게 지방에 돈을 분배했을때, 배정된 예산중 최댓값 정수를 출력하는 프로그램을 작성한다. 자세한 조건들과 설명은 위의 링크를 참조한다. 

1-2. 제한 사항

 - 첫 줄에는 지방 수를 의미하는 N이 주어지며, N은 3 이상 10,000 이하

 - 다음 줄에는 각 지방의 예산 요청을 표현하는 N개의 정수가 주어지며, 이 값들은 1 이상 100,000 이하

 - 그 다음 줄에는 총예산을 나타내는 정수 M이 주어지며, M은 N이상 1,000,000,000 이하

---

2. 구현

2-1. 풀이

각 지방 희망 예산의 최솟값과 최댓값을 구해 이진 탐색(이분 탐색)을 진행해야겠다고 마음먹었으나, 계속해서 50%에서 틀렸다. 무엇이 문제인지 살펴보니 지방 예산의 최솟값이 아닌 0을 넣었어야 함을 깨닫게 되었다. 각 지방이 원하는 희망 예산보다 적은 수가 나올 수 있다는 것을 뒤늦게 깨달았다.

예시를 들어보자면, N이 4이고 각 지방의 희망 예산이 10, 10, 10, 10 이며 M이 20 일때, 각 지방에 나눠줄 수 있는 최댓값은 5로 지방 희망 예산들보다 적은 숫자가 나오기 때문이다.

2-2. 코드 

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

constexpr size_t MAX_NUM = 10000;
int N, M, nums[MAX_NUM], maxNum = 0, result;

void binarySearch(int minNum, int maxNum);
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
        maxNum = max(maxNum, nums[i]);
    }
    
    cin >> M;

    binarySearch(0, maxNum);
    cout << result;
    return 0;
}

void binarySearch(int minNum, int maxNum) {
    int mid = (minNum + maxNum) / 2;
    int sumMax = 0;
    if (minNum <= maxNum) {
        for (int i = 0; i < N; i++) {
            if (nums[i] > mid) sumMax += mid;
            else sumMax += nums[i];
        }

        if (sumMax > M) return binarySearch(minNum, mid - 1);
        else {
            result = mid;
            return binarySearch(mid + 1, maxNum);
        }
    }
}