백준 2512번 예산

문제 링크입니다: https://www.acmicpc.net/problem/2512

문제를 잘 읽어야하는 이분 탐색 문제였습니다.

알고리즘은 아래와 같습니다.

1. 총액 이하에서 가능한 한 최대의 총 예산을 구하기 위해 입력받는 예산 요청 중 최대를 high로 두고 low를 0으로 둡니다.

2. 이분 탐색을 진행하는데 min(i 번째 예산 요청, 상한)을 다 더한 값이 M 이하이면 결과를 업데이트합니다.

3. 2번에서 구한 결과를 출력합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

vector<int> v;

 

long long calc(int num)

{

        long long result = 0;

        for (int i = 0; i < v.size(); i++)

                 result += min(v[i], num);

 

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        vector<int> v(N);

        int maxBudget = 0;

        for (int i = 0; i < N; i++)

        {

                 cin >> v[i];

                 maxBudget = max(maxBudget, v[i]);

        }

 

        int M;

        cin >> M;

 

        int low = 0, high = maxBudget;

        int result;

        while (low <= high)

        {

                 int mid = (low + high) / 2;

                 long long sum = 0;

                 for (int i = 0; i < N; i++)

                         sum += min(v[i], mid);

                 if (sum <= M)

                 {

                         result = mid;

                         low = mid + 1;

                 }

                 else

                         high = mid - 1;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~