[백준][C++]1202 - 보석 도둑

문제

• 1202번 : 보석 도둑
• Rank : Gold II
• 링크

1202번: 보석 도둑

풀이 전략

• 보석의 정보를 담은 구조체를 만들어 list에 입력받은 뒤, price 기준으로 정렬하여 비싼 보석부터 확인하였다.
  • bool operator<(const Jewel s) const를 구현하여 정렬
• 가방의 경우 multiset에 저장한 뒤, lower_bound를 사용하여 비싼 보석부터 하나씩 매칭.
• 보석을 전부 확인하거나, 가방이 가득 찬 경우 종료.

소스 코드

//Backjoon Problem No.1202
//Mist16, 2022-01-21

#include <iostream>
#include <list>
#include <set>
using namespace std;

struct Jewel
{
	int weight;
	int price;
	Jewel(int wei, int pri) : weight(wei), price(pri) {}

	//정렬시 price 기준으로 소트되도록 설정
	bool operator<(const Jewel s) const
	{
		return this->price > s.price;
	}
};

list<Jewel> jewels;
multiset<int> Bags;

int N, K;

int main()
{
	int tempWeight, tempValue;
	long long int totalPrice = 0;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> tempWeight >> tempValue;
		jewels.push_back(Jewel(tempWeight, tempValue));
	}
	for (int i = 0; i < K; i++)
	{
		cin >> tempWeight;
		Bags.insert(tempWeight);
	}
	jewels.sort();

	//가장 비싼 보석부터, 가능한한 가장 작은 가방에 적재
	for (auto iter1 = jewels.begin(); iter1 != jewels.end(); iter1++)
	{
		auto iter2 = Bags.lower_bound(iter1->weight);
		if (iter2 != Bags.end())
		{
			totalPrice += iter1->price;
			Bags.erase(iter2);
			//모든 가방이 찼을 경우 종료
			if (Bags.size() == 0)
			{
				cout << totalPrice;
				return 0;
			}
		}
	}
	cout << totalPrice;
	return 0;
}

 

여담

• 10만 개 이상의, 대량의 데이터를 가공하는 문제에서 자료구조 선택으로 인한 시간 문제가 발생하는 경우가 있다.
  • 각 자료구조별 순차접근/임의접근, 삽입/삭제 효율에 관해 정리해보는것도 좋을 듯.