백준 2512번 : 예산 (C 언어)

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

2512번: 예산

Code:

#include <stdio.h>
#include <limits.h>
 
int main()
{
    int n;
    scanf("%d", &n);
    long long arr[10001] = { 0, };
    long long sum = 0;
    int min = INT_MAX;
    int max = INT_MIN;
    long long result = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &arr[i]);
        sum += arr[i];
        if (max < arr[i])
        {
            max = arr[i];
        }
    }
    int m;
    scanf("%d", &m);
 
    if (sum <= m)
    {
        printf("%d", max);
    }
    else
    {
        long long first = 0;
        long long end = m;
        int flag = 0;
        while (first <= end)
        {
            long long mid = (first + end) / 2;
            long long temp = 0;
            for (int i = 0; i < n; i++)
            {
                if (arr[i] <= mid)
                {
                    temp += arr[i];
                }
                else
                {
                    temp += mid;
                }
            }
                if (temp <= m)
                {
                    result = mid;
                    first = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
        }
        printf("%lld", result);
    }
}

문제풀이

이분탐색을 이용해서 문제를 풀이하였다.

예산이 n개가 주어지면 예산을 모두 더한것이 m보다 작을 시 max값을 출력해주고 m보다 클 시에 이분탐색으로 상한선을 찾아준다.

first는 0으로 end는 m으로 잡아서 상한선을 찾는다.