[BaekJoon][2512] 예산

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2012

2512 예산

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

정답 찾아가는 이진 탐색

#include <stdio.h>
 
int n;
int cost[10000];
int limit;
int sum[10001];
int max;
 
void solve()
{
    int s = 0, e = max, m;
    int cal, num;
    int i;
 
    while (s <= e) {
        m = (s + e) / 2;
 
        cal = 0;
        for (i = 0; i < n; i++) {
            if (cost[i] > m)    cal += m;
            else                cal += cost[i];
        }
 
        if (cal > limit)    e = m - 1;
        else                s = m + 1;
    }
 
    printf("%d\n", e);
}
 
int main()
{
    int i;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &cost[i]);
        if (cost[i] > max)    max = cost[i];
    }
    scanf("%d", &limit);
 
    solve();
 
    return 0;
}