[C/C++] 백준 #2512 예산(이분 탐색)

이번 문제는 예산이 요청되었을 때, 정해진 예산에 맞추어 최대 허용 예산값을 구하는 문제입니다.

 

budget

 

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

2512번: 예산

 

이 문제는 최대 허용 예산값에 대해서 전체 예산 요청들을 만족하는지 아닌지를 판단할 수 있습니다.  최대 허용 예산값이 커질 수록 당연히 예산 초과가 될 수 있고, 최대 허용 예산값이 작아질수록 예산이 만족하기 때문에 어떤 값 이하에서는 항상 조건을 만족하고 그것을 초과하는 경우에는 항상 조건을 만족하지 않는 것이 존재하게 됩니다.  이런 경우 적용하는 알고리즘으로 이분 탐색이 있습니다.

 

이전에 제가 풀어본 이분 탐색 문제입니다.

https://sdev.tistory.com/1174

[C/C++] 백준 #2110 공유기 설치(이분 탐색)

https://sdev.tistory.com/1059

[C/C++] 백준 #1981 배열에서 이동(이분탐색)

 

초기의 왼쪽값과 오른쪽값을 정할 때, 왼쪽값은 전체 예산을 n으로 나눈 값으로 하였습니다.  그 경우에는 무조건 예산을 충족하니까요.  오른쪽 값은 예산안 중 가장 큰 값으로 설정했습니다.  예산이 충분하다면, 가장 큰 값이 답이 됩니다.

 

제가 작성한 소스입니다.

//-------------------------------------------
//    baekjoon #2512
//        - by Aubrey Choi
//        - created at 2019-10-26
//-------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, v[10000], l, r=0, s=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) { scanf("%d",&v[i]); s+=v[i]; if(v[i]>r) r=v[i]; }
    scanf("%d",&m); l=m/n;
    if(s<=m) { printf("%d\n",r); return 0; }
    while(l<r-1)
    {
        int c=(l+r)/2, sum=0;
        for(int i=0;i<n;i++) sum+=v[i]<c?v[i]:c;
        if(sum<=m) l=c; else r=c;
    }
    printf("%d\n", l);
}