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

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

17503번: 맥주 축제

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

 

먼저 해당 포스트에서는 우선순위 큐를 이용하여 풀이한 것을 첨부합니다.

(이분 탐색을 이용한 풀이는 https://jinho9610.tistory.com/35를 참고해주세요.)

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

 

이분 탐색을 이용해서 문제를 푸는 것보다 효율적인 풀이가 있길래 적용 후 포스팅을 진행한다.

 

이분 탐색은 말그대로 "정답이 되는 경우를 탐색"하는 느낌이라면 우선 순위 큐 풀이는 "실제로 술을 하나씩 담아가면서 목표한 바를 달성하면 중단"하는 방식의 풀이이다.

 

코드의 주석이 현재 포스팅할 수 있는 최고의 설명이라고 생각되어, 별도의 첨언을 하지 안는다.

(이게 뭐지? 싶은 부분은 아마 sort를 위한 람다 함수와 pq의 삽입 시 비교 방식인 cmp 구조체일 것인데 관련 포스팅은 구글의 도움의 받기를 추천한다!)

 

/* 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<int, int>> beers;
 
struct cmp
{
    bool operator()(int a, int b)
    {
        return a > b;
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < k; i++)
    {
        int v, c;
        cin >> v >> c;
        beers.push_back({v, c}); // 선호도, 도수 레벨
    }
 
    sort(beers.begin(), beers.end(), [](pair<int, int> p1, pair<int, int> p2) -> bool
         { return p1.second < p2.second; }); // 술 도수 레벨 기준 오름차순 정렬
 
    priority_queue<int, vector<int>, cmp> pq; // 맥주 담을 주머니
 
    ll total = 0;
    for (auto beer : beers)
    {
        pq.push(beer.first); // 현재 맥주를 주머니에 담기 (맥주의 선호도로 해당 맥주 표현)
        total += beer.first; // 현재 주머니에 담긴 맥주들의 선호도 총 합
 
        if (pq.size() > n) // 이미 술이 n개 선택된 상황이었다면
        {
            // (직전의 삽입으로 주머니에 n + 1개의 맥주가 담겨있다면)
            total -= pq.top(); // 가장 작은 선호도의 술을 뺀다
            pq.pop();
        }
 
        // 주머니에 술이 n개 담겨있고, 담긴 술들의 선호도 총 합이 m 이상이라면
        if (pq.size() == n && total >= m)
        {
            cout << beer.second << endl; // 방금 넣은 맥주의 도수 레벨이 정답이므로 출력
            return 0;
        }
    }
    cout << -1 << endl; // 정답을 찾지 못한 경우 -1 출력
 
    return 0;
}