[C++] 백준 2512 - 예산

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

2512번: 예산

<풀이>

1. 주어진 입력 값들로 모든 예산 요청이 배정될 수 있는지 없는지를 판단하여 결과를 출력한다.

​

<해법>

1. 모든 예산 요청이 배정될 수 없는경우 -> 상한액 설정하는 방법.

=> 모든 상한액들을 탐색해 보아야 합니다. 이 때 상한액의 범위를 생각해 보아야 합니다. 상한액의 범위는 0부터 요청한 예산 중 가장 큰 값 사이에 있습니다. 이 범위 사이에서 이분탐색 알고리즘을 이용해, 상한액을 찾습니다.

#include <iostream>
using namespace std;
 
int main() {
 
    int N;
    int arr[10000];
    long long M;
 
    //처음 요청 금액의 합
    long long first_req_sum = 0;
    //요청 금액 중 가장 큰 금액
    int biggest = 0;
    long long res = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        first_req_sum += arr[i];
        if (arr[i] > biggest) {
            biggest = arr[i];
        }
    }
    cin >> M;
 
    //모든 요청이 배정될 수 있는 경우 -> 1번 조건
    if (first_req_sum <= M) {
        res = biggest;
    }
    //모든 요청이 배정될 수 없는 경우 -> 2번 조건 -> 상한액 찾기
    else {
        //상한액 : 0 ~ biggest
        int str = 0;
        int fin = biggest;
 
        //이분 탐색
        while (str <= fin) {
 
            int mid = (str + fin) / 2;
 
            long long tmpSum = 0;
            for (int i = 0; i < N; i++) {
                if (arr[i] < mid) {
                    tmpSum += arr[i];
                }
                else {
                    tmpSum += mid;
                }
            }
 
            if (tmpSum > M) {
                fin = mid - 1;
            }
            else if (tmpSum < M) {
                str = mid + 1;
                res = mid;
            }
            //모든 예산을 다 사용할 수 있는 경우
            else {
                res = mid;
                break;
            }
        }
    }
 
    //출력
    cout << res;
 
    return 0;
}

 

이분탐색에 대해 알아볼 수 있는 문제였습니다.