✅ 이진탐색

문제

링크

1. 문제 접근 및 해결 로직

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
   -> 상한액은 요청한 금액 중 최댓값
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
   -> 모든 요청이 배정될 수 없다는 것은 요청 금액의 합이 국가 예산 총합을 넘는다는 것이므로 상한액을 따로 구해야 한다.

요청 예산의 최댓값은 100,000이고 지방 수의 최댓값은 10,000이므로
예산을 하나씩 줄여가며 각 지방의 예산을 구한뒤 국가 예산의 총합을 넘는지 안넘는지 판별하려면 최악의 경우 너무 많은 연산을 해야한다.

따라서 상한액을 반씩 줄여가며 이진탐색으로 구현했다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int arr[10001], N, M, sum = 0;
int low, high, mid;

bool is_possible()
{
    sum = 0;
    for (int i = 0; i < N; i++)
    {
        if (arr[i] > mid)
            sum += mid;
        else
            sum += arr[i];
    }
    
    // cout << "sum : " << sum << " high : " << high << " mid : " << mid << "\n";

    if (sum <= M)
        return true;
    else return false;
}

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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    cin >> M;

    if (sum <= M) // 모든 요청이 배정될 수 있는 경우
    {
        cout << *max_element(arr, arr + N) << "\n";
        return 0;
    }

    sort(arr, arr+N);
    
    low = 1;
    high = arr[N-1];
    mid = (low + high) / 2;

    while (low <= high) // high : 4, low : 4 일때 high(=mid)도 판별해봐야 하므로 < 가 아닌, <= 까지 반복문 수행
    {
        if (is_possible())
        {
            low = mid+1;
            mid = (low + high) / 2;
        }
        else
        {
            high = mid-1;
            mid = (low + high) / 2;
        }
    }
    
    cout << high << "\n";

    return 0;
}

3. 시간 복잡도 분석

$O(log_2N)$

4. 문제에서 중요한 부분

선형완전탐색으로는 풀기 힘드므로 이진탐색을 떠올리는 것이 중요했고
언제까지 이진탐색을 수행할껀지 반복문의 조건을 실수할뻔 했었음
high : 4, low : 4 일때 high(=mid)도 판별해봐야 하므로 low < high 가 아닌, low <= high 까지 반복문 수행