2512번 예산

전형적인 이분 탐색이다.

구현을 하면서, 1부터 탐색하여 입력한 숫자들 중의 최댓값까지

직접 탐색을 하니, 시간 초과가 뜰 것 같았는데 다행히 통과되었다.

20번 째 while 조건 left < right가 아니라 left <= right 이다.

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

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
vector<int> v;
 
int sum = 0;
 
int bs(int left, int right)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;
        int s = 0;
 
        for (int i = 0; i < v.size(); i++)
        {
            int add = v.at(i);
 
            if (middle <= add) add = middle;
 
            s += add;
        }
 
        if (s == sum) return middle;
        else if (s > sum) --right;
        else ++left;
    }
 
    return right;
}
 
int main(void)
{
    int N = 0, money = 0, MAX = INT32_MIN;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &money);
 
        MAX = max(money, MAX);
 
        v.push_back(money);
    }
 
    scanf("%d", &sum);
 
    printf("%d\n", bs(1, MAX));
 
    return 0;
}