[BOJ 2512] 예산

문제 출저 : https://www.acmicpc.net/problem/2512

 

풀이 : 

 

이분 탐색 문제입니다.

배정 될 수 있는 예산들 중 최댓값은 요청의 최댓값을 넘을 수 없기 때문에 e를 요청중 최댓값으로 설정합니다.

mid를 요청 당 최대로 배정할 예산으로 두고 아래와 같이 계산합니다.

1. 요청 당 배정할 예산 >= 요청 : 요청만큼 배정

2. 요청 당 배정할 예산 < 요청 : 배정할 예산만큼 배정

 

그 후 현재 배정된 총 예산과 총 예산과 비교하고 아래와 같이 이분탐색을 실행합니다

1. 배정된 총 예산 <= 총 예산 : parametricSearch(mid + 1, e);

2. 배정된 총 예산 > 총 예산 : parametricSearch(s, mid - 1);

 

배정된 총 예산이 총 예산보다 작다면 예산을 조금 더 배정 할 수 있다는 말이 되므로 예산을 더 늘려서 이분 탐색을 진행하고, 반대의 경우에는 예산을 더 적게 배정 해야 한다는 말이 되므로 예산을 줄여서 이분탐색을 진행합니다.

 

#include<stdio.h>
 
int n,m,arr[10000],check,Max,result;
 
void parametricSearch(int s,int e)
{
    if (s > e)return;
    int ret = 0,mid=(s+e)/2;
    for (int i = 0; i < n; i++)
    {
        if (mid >= arr[i])ret += arr[i];
        else ret += mid;
    }
    if (ret <= m)
    {
        if (result < mid)result = mid;
        parametricSearch(mid + 1, e);
    }
    else parametricSearch(s, mid - 1);
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        if (arr[i] > Max)Max = arr[i];
        check += arr[i];
    }
    scanf("%d", &m);
    if (m >= check)result = Max;
    else parametricSearch(0, Max);
    printf("%d",result);
}