[백준] 3691: 컴퓨터 조립

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

3691번: 컴퓨터 조립

지금 생각하면 왜 그렇게 고민을 했나 의문스러운 문제이다.

여기서는 전체 성능을 어떻게 측정하는가가 관건이다.

전체 성능은 곧 구성하는 부품들 중 가장 낮은 성능이다.

그래서 전체 성능을 높이기 위해서는 가장 낮은 성능을 최대한 높여야 한다.

 

그래서 구성 부품들을 낮은 성능부터 교체하기 위해 최소 힙을 사용하여 정렬한다.

그리고 부품들은 부품별로 가격 오름차순으로 정렬해놓는다. 그래야 동일한 성능이 있더라도 가격이 더 저렴한 부품에 먼저 접근하기 때문이다.

그래서 가장 낮은 성능을 가진 부품을 찾으면, 해당 부품과 동일한 유형의 부품의 최소힙으로 접근하여 성능이 더 높은지(성능이 동일하면 굳이 바꿀 필요가 없기 때문), 구매 가능한 부품인지 확인하고 교체한다.

워낙 자료구조가 중첩이 많이 되어서 복잡할 수 있으니 네이밍에 주의하고, 주석을 잘 활용하면 좋을 거 같다.

그리고 놓칠 수 있는 조건들을 확인해야 한다.

해당 부품을 모두 탐색했으나 결국 예산의 문제로 교체가 되지 않는 경우를 확인하는 것도 잊지않아야 한다.(bool changed)

/**
 * https://www.acmicpc.net/problem/3691
 * 우선 가장 저렴한 부품들로 구성한 뒤 성능이 낮은 부품부터 교체
*/

#include <iostream>
#include <map>
#include <queue>
#include <tuple>
using namespace std;

int main() {
    int t, n;
    long long b;
    cin >> t;
    while(t--) {
        string type, name;
        long long price, quality;
        // 성능, 가격, 종류 -> 선택한 부품들을 성능 오름차순 정렬(가장 낮은 성능이 곧 전체의 성능이므로 성능 낮은 것부터 교체하기 위함)
        priority_queue<tuple<long long, long long, string>, vector<tuple<long long, long long, string>>, greater<tuple<long long, long long, string>>> selection;
        // 가격, 성능 -> 부품별로(key) 가격 오름차순으로 부품 정렬
        map<string, priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>> products;
        cin >> n >> b;
        for(int i = 0;i < n;i++) {
            cin >> type >> name >> price >> quality;
            products[type].push({price, quality});
        }
        long long total_price = 0;
        long long lowest_quality = 1 << 9;
        for(auto product : products) {
            pair<long long, long long> p = product.second.top();
            total_price += p.first;
            // 부품 중 가장 낮은 성능
            lowest_quality = min(lowest_quality, p.second);
            selection.push({p.second, p.first, product.first});
        }

        while(b >= total_price) {
            bool changed = false;
            auto product = selection.top();
            tie(quality, price, type) = product;

            // 부품 중 가장 낮은 성능 확정
            if(products[type].empty()) break;


            while(!products[type].empty()) {
                auto cmp_product = products[type].top();
                products[type].pop();
                // 성능이 가장 나쁜 부품을 업그레이드할 수 있는 경우
                if(quality < cmp_product.second && total_price - price + cmp_product.first <= b) {
                    // 교체 작업
                    total_price = total_price - price + cmp_product.first;
                    selection.pop();
                    selection.push({cmp_product.second, cmp_product.first, type});
                    changed = true;
                    break;
                }
            }
            // 해당 부품의 큐를 모두 탐색했으나 예산 범위 내에서 업그레이드 실패
            if(!changed) break;
        }

        tie(quality, price, type) = selection.top();
        cout << quality << '\n';
    }
}