[2512번] 예산

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 탐색

예산의 최대치를 알아야 하는 문제이다.

이때 예산은 무조건 지방 예산 요청의 0과 최댓값 사이에 존재한다.

따라서 이 문제를 이분 탐색을 이용하여 정부의 예산을 결정할 수 있다.

start, end를 정부 예산 범위로 지정하고 mid를 최종적으로 지방에게 나누어줄 예산으로 지정한다.

그렇게 되면 start = 0부터, end = 예산요청중 최댓값으로 시작한다.

이제 get이라는 변수를 두어 이분 탐색에서 mid라는 예산으로 가정했을 때 총 예산을 계산해본다.

결국 get이라는 변수와 total 변수를 이용하여 end와 start를 계속해서 조절 할 수 있다.

만약 get > total(총합이 정부 총 예산을 초과)인데 start와 end가 같다면

start와 end를 하나씩 줄여가며 확인해주면 된다.

결국 이를 통해 mid가 답이 될 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int arr[10002];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    sort(arr, arr + n);
 
    int total;
    scanf("%d", &total);
 
    int start = 0, end = arr[n - 1];
    int mid = (start + end) / 2;
 
    while (start <= end)
    {
        mid = (start + end) / 2;
 
        // 현재 mid를 예산으로 가정하고 총 예산을 구한다.
        int get = 0;
        for (int i = 0; i < n; i++)
            mid > arr[i] ? get += arr[i] : get += mid;
    
        // 여전히 총 예산이 총 금액보다 큰데 end와 start가 같다면
        // 하나씩 내려가본다.
        if (get > total && end == start)
            end--, start--;
 
        // 총 예산이 총 금액보다 크면 end = mid
        else if (get > total)
            end = mid;
 
        // 총 예산이 총 금액보다 작거나 같다면 start = mid + 1
        else
            start = mid + 1;
    }
 
    printf("%d", mid);
 
    return 0;
}
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>