[백준/BOJ] 백준 3691번 : 컴퓨터 조립

www.acmicpc.net/problem/3691

3691번: 컴퓨터 조립

각 제품마다 번호를 붙이고, 각 제품마다 (-가격,품질) 우선순위 큐를 만든다 (가격이 낮은거 부터, 가격이 동점일 땐 품질인 큰 거 꺼내기 위해) 그리고 컴퓨터를 만들때 사용하는 부품을 저장하는데, (-품질,(부품번호,가격))를 통해 저장한다 (품질이 작은 부품부터 꺼내기 위해) 우선 최소 가격으로 만들 수 있는 컴퓨터를 만든다. 그리고 컴퓨터에 속한 가장 작은 퀄리티의 부품을 하나씩 더 좋은 퀄리티로 바꿔가는 것을 예산을 넘지 않을 때까지 진행한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
using namespace std;

int tc;
int result;

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

	cin >> tc;
	cin.ignore();

	for (int t = 0; t < tc; t++)
	{
		int n, b;
		map<string, int> product_number; //각 제품마다 번호를 붙인다
		map<string, int>::iterator it;
		int check_number = 0;
		priority_queue<pair<int, int>> pq[1001]; //각 제품마다 (-가격,품질) 우선순위 큐를 만든다 (가격이 낮은거 부터, 가격이 동점일땐 품질인 큰거 꺼내기 위해)
		priority_queue<pair<int, pair<int, int>>> computer; //컴퓨터가 만들어지는 부품을 저장하는데, (-품질,(부품번호,가격))를 통해 저장한다 (품질이 작은 부품부터 꺼내기 위해)

		cin >> n >> b;
		cin.ignore();

		for (int i = 0; i < n; i++)
		{
			string input;
			getline(cin, input);

			vector<string> info;
			for (int j = 0; j < 3; j++)
			{
				int index = input.find(" ");
				info.push_back(input.substr(0, index));

				input = input.substr(index + 1);
			}
			info.push_back(input);

			string type = info[0];
			string name = info[1];
			int price = stoi(info[2]);
			int quality = stoi(info[3]);

			it = product_number.lower_bound(type);

			//처음 발견한 부품일때, 부품의 종류에 번호를 매긴다
			if (it == product_number.end() || (*it).first != type)
			{
				check_number++;//부품을 1번부터 번호를 매긴다
				product_number.insert(make_pair(type, check_number));
			}

			//각 제품 우선순위큐에 (-가격,품질)순으로 저장한다
			pq[product_number[type]].push(make_pair(-price, quality));
		}

		//최소 가격으로 만들 수 있는 컴퓨터의 부품들정보와, 가격을 구한다
		int computer_price = 0;
		for (int i = 1; i <= check_number; i++)
		{
			int this_product_number = i;
			int this_product_price = -pq[i].top().first;
			int this_product_quality = pq[i].top().second;
			pq[i].pop();

			computer_price += this_product_price;
			computer.push(make_pair(-this_product_quality, make_pair(this_product_number, this_product_price))); //만들어지는 부품 정보 저장
		}

		while (computer_price <= b)
		{
			result = -computer.top().first; //부품 중 가장 작은 퀄리티가 컴퓨터의 성능

			int min_quality = -computer.top().first; //부품중 가장 작은 퀄리티 부품의 퀄리티
			int min_quality_number = computer.top().second.first; //부품중 가장 작은 퀄리티 부품의 번호
			int min_quality_price = computer.top().second.second; //부품중 가장 작은 퀄리티 부품의 가격
			computer.pop();

			//해당 부품의 퀄리티가 더 큰거를 가격이 낮은 순서대로 찾는다
			while (pq[min_quality_number].size() != 0 && pq[min_quality_number].top().second <= min_quality)
			{
				pq[min_quality_number].pop();
			}

			//적절한 부품이 없을때
			if (pq[min_quality_number].size() == 0)
				break;

			//적절한 부품이 있을때
			else
			{
				int buy_product_quality = pq[min_quality_number].top().second;
				int buy_product_price = -pq[min_quality_number].top().first;
				pq[min_quality_number].pop();

				computer_price -= min_quality_price;
				computer_price += buy_product_price;

				computer.push(make_pair(-buy_product_quality, make_pair(min_quality_number, buy_product_price)));
			}
		}

		cout << result << "\n";
	}

	return 0;
}