[BOJ알고리즘, C++]#2512_예산, 이분 탐색, Binary Search

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 이분 탐색

[알고리즘]#1_이분 탐색(Binary Search)

이분 탐색은 주어진 정렬된 배열에서 특정 값을 찾기 위해 활용하는 탐색 알고리즘입니다. 주어진 배열에서 왼쪽 경계와 오른쪽 경계를 설정하고, 이 중간 값을 찾고자 하는 값과 비교하며 왼쪽 경계 혹은 오른쪽 경계를 수정하며 최종적으로 중간 값이 찾고자 하는 값과 같을 때까지 이 작업을 반복합니다. 

 

2. 요청 금액이 예산보다 크면 오른쪽 경계 땡겨 오기, 아니면 왼쪽 경계 당겨 오기

1. 먼저, 요청 예산 금액 목록을 오름차순 정렬합니다.
2. 요청 금액 목록의 0번째 인덱스를 왼쪽 경계, 그리고 가장 마지막 인덱스를 오른쪽 경계로 설정합니다.
3. 중간 값을 계산하고, 이를 기준으로 요청 금액이 더 크다면 그대로 중간 값을, 아니라면 요청 금액을 누적해서 더해줍니다.
4. 만약, 총 예산 요청 금액이 M보다 크다면 오른쪽 경계를 mid-1 위치로 당겨줍니다.
5. 만약, 총예산 요청 금액이 M보다 적거나, 같다면 최종 요청 금액을 업데이트해주고, 왼쪽 경계를 mid + 1 위치로 당겨줍니다.
6. 주의할 점은 총예산 요청 금액이 M보다 적거나, 같다면 결과 값을 업데이트해주고 이분 탐색을 멈추면 안 됩니다! 최적의 값을 찾기 위해 모든 경우의 수를 비교해보아야 합니다. 왼쪽 경계를 mid - 1 위치로 옮긴 이상 M보다 작거나 같은 경우에 그 최종 예산 금액이 이전에 계산한 최종 금액 보다 무조건 작기 때문이죠!

 

---

 

#3. 코드

/*
    @문제: 주어진 예산을 활용해 각 지방의 요청 예산의 상한액의 최대 값
    @설명
        1. 상한액이 주어지면, 이보다 작을 경우 요청 금액을 그대로 받고, 이보다 클 경우 상한액이 주어진다.
        2. 각 지방의 예산의 최소 값을 Left 최대 값을 Right 경계로 지정하고, 이분 탐색을 수행한다.
        3. 주의할점: 최소 값을 Left(왼쪽 경계)로 설정할 경우, 예산이 적을 경우 정답을 도출할 수 없을 수 있다.
        4. 주의할점: mid를 통해 계산 된 예상 상한액과 M을 비교할 때, 두 값이 같을 때에도 최적의 값을 찾기 위해 반복문을 지속해야하므로, 적거나 같을 경우로 취급한다.
*/

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long ll;

ll N, M;
vector<ll> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    while(N--)
    {
        ll money;
        cin >> money;

        v.push_back(money);
    }

    cin >> M;

    // 1. 정렬
    sort(begin(v), end(v));

    // 2. 이분 탐색
    ll left = 0;
    ll right = v.back();
    ll res = 0;

    while(left <= right)
    {
        // 가운데 값
        ll mid = (left + right)/2;
        ll total = 0;
        // 가운데 값을 상한액으로 하는 총 예산 요청 금액
        for(int i=0; i<v.size(); ++i)
            total += min(v[i], mid);
        
        // 만약, 요청 예산 금액이 예산보다 클 경우: 오른쪽 경계를 mid-1로 옮겨준다.
        if(total > M)
        {
            right = mid-1;
        }
        // 만약, 요청 예산 금액이 예산보다 적을 경우: 왼쪽 경계를 mid+1로 옮겨주고, 최대 상한액 업데이트
        else if(total <= M)
        {
            res = mid;
            left = mid+1;
        }
    }

     cout << res;

    return 0;
}

 

---