백준(BOJ) 17503 맥주 축제 C++ (이분 탐색) 풀이

문제 링크: https://www.acmicpc.net/problem/17503

17503번: 맥주 축제

풀이에 이용된 알고리즘: 이분 탐색, 우선 순위 큐

 

먼저 해당 포스트에서는 이분 탐색을 이용하여 풀이한 것을 첨부합니다.

(우선 순위 큐를 이용한 풀이는 https://jinho9610.tistory.com/36를 참고해주세요.)

백준(BOJ) 17503 맥주 축제 C++ (우선순위 큐) 풀이

 

최소 도수 레벨을 1부터 1씩 증가시켜나가며 정답을 찾는 방법이 가장 먼저 떠오를 수 있지만, 탐색 범위가 너무 넓기 때문에 시간 초과가 날 것을 예상할 수 있다.

 

또한 해당 도수 레벨보다 낮은 도수 레벨을 갖는 술 중에서 높은 선호도를 갖는 n개의 술을 골라내야 하는데 이런 추가적인 연산까지 고려하면 당연히 시간 초과가 발생한다.

 

넓은 탐색 영역에서 조금이라도 효율적으로 정답 도수 레벨을 찾기 위해서 이분 탐색을 진행하였다.

 

대부분의 설명은 코드에 주석으로 첨부하였으므로 하기의 코드와 함께 보는 것을 추천한다.

 

상위 n개의 선호도 만을 합하여 목표 선호도인 m과 비교하는데, 여기서 상위 n개 만을 고려하는 이유는 가장 작은 레벨의 도수 레벨을 찾는 입장에서, 매 탐색 시 최대의 선호도를 계산하여 m과 비교하는 것이 합리적이기 때문이다.

 

예를들어 도수 레벨 a보다 낮은 술들의 선호도가 3 5 7 8 1 12인데, 이 중 임의로 3개의 술을 선택하여 그 선호도의 합이 10을 넘기는 경우 탐색을 중단한다고 하면, 12 8 7을 선택하는 것이 합리적이지 1 3 5를 선택하는 것은 비합리적이기 때문이다.

 

/* BOJ 17503 맥주 축제 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int n, m, k;
vector<pair<ll, ll>> beers;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m >> k;
 
    int c_max = 0; // 도수 레벨 중 최대 값
    for (int i = 0; i < k; i++)
    {
        int v, c;
        cin >> v >> c;
        beers.push_back({v, c}); // 선호도, 도수 레벨
        c_max = max(c_max, c);   // 탐색 범위의 maximum 값
    }
 
    sort(beers.begin(), beers.end(), [](pair<ll, ll> p1, pair<ll, ll> p2) -> bool
         { return p1.second < p2.second; }); // 술 도수 레벨 기준 오름차순 정렬
 
    ll ans = 1e13;
    ll left_idx = 1, right_idx = c_max; // 탐새 범위 초기화
    while (left_idx <= right_idx)
    {
        ll mid = (left_idx + right_idx) / 2;
 
        ll total = 0;
        vector<ll> candis;
        for (auto beer : beers)
        {
            if (beer.second > mid) // 오름차순 정렬이므로 더이상 탐색 필요 x
                break;
 
            candis.push_back(beer.first);
        }
 
        if (candis.size() < n) // 마실 수 있는 맥주가 n개 조차 안되는 상황
        {
            left_idx = mid + 1; // 도수 레벨을 조금 더 증가시키는 방향으로
            continue;           // 탐색 이어나가기
        }
 
        sort(candis.begin(), candis.end(), [](ll a, ll b) -> bool
             { return a > b; }); // 도수 레벨 mid 보다 낮은 도수 레벨의 술을 선호도 기준 내림차순 정렬
 
        for (int i = 0; i < n; i++)
            total += candis[i]; // 상위 n개의 선호도 합 계산
 
        if (total < m)          // 상위 n개의 선호도가 m보다 작다면
            left_idx = mid + 1; // 도수 레벨을 조금 더 증가시키는 방향으로 탐색 이어나가기
        else
        {
            right_idx = mid - 1; // 도수 레벨을 조금 더 감소시키는 방향으로 탐색 이어나가기
            ans = min(ans, mid); // 최소 도수 레벨(정답) 갱신
        }
    }
 
    cout << (ans != 1e13 ? ans : -1) << endl;
 
    return 0;
}