[백준/Baekjoon] 17503 맥주 축제 C++ :: Data structure & Binary Search

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

17503번: 맥주 축제

---

1. Logic

우선순위 큐와 이진탐색으로 푸는 방법이 있는데 나는 그리디적으로 접근해서 우선순위 큐를 이용해서 풀었다. 사실 이분탐색은 계속 실패해서,, // 이분탐색으로도 풀었다!! 

우선순위 큐 풀이 방법은 

1. pair를 원소로 가지는 vector에 {도수, 선호도}로 입력하고 오름차순으로 정렬한다. > 도수기준 오름차순 정렬

2. 선호도를 sum에다 누적해주고 우선순위 큐에 도수가 낮은거부터 순서대로 선호도에 -를 붙혀서 오름차순으로 정렬해준다. 

3. 우선순위 큐pq의 사이즈 pq.size()값이 n이랑 같아지면 sum이 m 이상인지 확인 후 이상이면 현재 beer의 도수를 출력한다. 이유는 beer 벡터를 알콜 도수가 높은 순서대로 알콜도수 기준 오름차순 정리를 했기 때문에 지금 조건의 알콜 도수가 최소 도수이다.

4. 만약 3번에서 안걸러지고 우선순위 큐의 갯수가 n을 넘었다면 pq.top()값(가장 선호도가 낮은 값)을 sum에서 더해준다(넣을 때 -를 붙혀서 넣었기 때문에 사실 빼주는 거임). 그리고 pq.pop을 해준다. 이후 다시 3번을 검사한다.

 

이분탐색 풀이방법은 

1. 이분탐색으로 찾는 mid값은 도수레벨을 의미한다.

2. 이분탐색 루프에 들어가기 전에 check(end)값(끝 극값)이 true가 나오면 간 레벨이 아무리 높아도 만족도를 못 채우는것이기 때문에 -1을 바로 반환한다. 통과했다면 이분탐색 루프를 들어간다.

3. 알콜 낮은 순서대로 정렬을 한 상태에서 mid값을 check함수로 확인한다.

4. check함수에서는 mid값보다 도수가 같거나 작은 값만 선호도를 temp벡터에 저장하고 temp의 갯수가 n보다 작으면 무제의 기준을 만족 못하기 때문에 true를 반환하여 간 레벨을 올려준다.

5. 선호도가 담긴 temp배열을 내림차순으로 정리한 후 큰 값부터 n개만큼 선택해 주고 선택한 sum에 더해준다.

6. sum이 m보다 작으면 선호도를 못 채웠기 때문에 true를 반환하여 간 레벨을 올려주고 sum보다 크거나 같으면 false를 반환하여 간 레벨을 낮춰준다. sum과 m이 같더라도 우리는 최소 간 레벨을 구해야 하기 때문에 줄여준다.

 

처음에 이분탐색으로 문제가 엄청 안풀렸는데 그 이유는 mid는 여러가지 값으로 바뀌면서 sum값이 달라지는데 mid는 항상 초기 end값 미만이다. 그래서 mid는 어떤 일이 있어도 end이상의 값을 가지지 못하기 때문에 루프 안의 mid는 end-1의 값 까지만 테스트 하느라 sum안에는 m미만의 값만 들어갈 수밖에 없다.

---

2. Code

우선순위 큐를 활용한 풀이

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

long long n, m, k;

vector<pair<long long, long long>> beer;
priority_queue<long long> pq;

bool compare(pair<long long, long long> & a, pair<long long, long long> &b) {
    if(a.first < b.first) return true;
    else if(a.first == b.first) return a.second > b.second;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    cin >> n >> m >> k;
    
    for(int i = 0; i < k; i++) {
        long long prefer, alc;
        cin >> prefer >> alc;
        beer.push_back({alc, prefer});
    }
    sort(beer.begin(), beer.end(), compare);
    
    long long sum = 0;
    
    for(int i = 0; i < k; i++) {
        //도수가 낮은거부터 빼려고
        pq.push(-beer[i].second);
        sum += beer[i].second;
        
        if(pq.size() > n) {
            sum += pq.top();
            pq.pop();
        }
        
        //큰 값으로 정렬해놨기 때문에 i가 커질수록 큰 값만 반환함
        if(pq.size() == n && sum >= m) {
            cout << beer[i].first;
            return 0;
        }
    }

    cout << -1;
}

 

Binary Search를 활용한 풀이

#include <bits/stdc++.h>

using namespace std;

long long n, m, k;

vector<pair<long long, long long>> beer;

bool check(int mid) {
    vector<long long> temp;
    long long sum = 0;
    
    for(int i = 0; i < k; i++) {
        if(beer[i].first <= mid) {
            temp.push_back(beer[i].second);
        }
    }
    
    if(temp.size() < n) return true;
    
    sort(temp.begin(), temp.end(), greater<long long>());
        
    for(int i = 0; i < n; i++) {
        sum += temp[i];
    }
    
    if(sum < m) return true;
    else return false;
}

long long binarySearch() {
    long long start = 0;
    long long end = INT_MAX;
    long long mid;
    if(check(end)) return -1;
    while(start + 1 < end) {
        mid = (start + end) / 2;
        
        if(check(mid)) start = mid;
        else end = mid;
    }
    
    
    return end; 
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    
    for(int i = 0; i < k; i++) {
        long long prefer, alc;
        cin >> prefer >> alc;
        
        beer.push_back({alc, prefer});
    }
    
    sort(beer.begin(), beer.end());
    
    cout << binarySearch();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐