[GOLD 2] 보석 도둑

1. 문제 링크

문제 링크

---

2. 문제 이해 및 풀이 전략

여러 { 무게, 가치 }를 가진 보석을 서로 다른 { 무게 }를 가진 가방에 각각 1개 씩 넣을 때 가장 큰 가치를 산출하는 문제.

각 가방에는한 개의 보석만 넣을 수 있기 때문에 조건은 간단하다.

 

가장 간단하게 떠오른 방법으로 가벼운 무게 순으로 보석과 가방을 정렬해 가방을 기준으로 담을 수 있는 가장 가치가 큰 보석을 차례로 담고 가치의 합을 구하는 방법을 구상했다. 

1. 보석과 가방을 우선순위 큐에 담아 무게가 작은 순으로 정렬
2. 정렬된 가방을 기준으로 담을 수 있는 무게의 보석 중 가장 가치가 큰 보석을 저장
3. 저장된 보석들의 가치를 합산

 

시행 착오

보석과 배낭의 정보를 저장할 구조를 우선순위 큐로 하니 가장 가벼운 무게의 보석과 가방을 특정하기는 쉬웠지만, 현재 가방에 보석이 담기지 않아 다음 가방을 생각해야 할 경우가 어려워졌다.

 

때문에 보석과 배낭을 일반 Vector에 담아 무게가 적은 순으로 정렬하고 가방에 담길 수있는 후보로 선택될 보석들을 우선순위 큐에 가치 순으로 저장했다.

 

* 보석들을 우선순위 큐에 담은 이유 ?

       현재 가방에 담기지 않앗더라도 다음 가방은 현재 가방보다 허용 무게가 큰 가방이기 때문에 언제든 후보로 선택된 보석들을 담을 수 있         다. 때문에 지금까지 등장한 가방의 무게보다 작거나 같은 보석들을 다시 한번 가치 순으로 정렬해 가장 가치가 큰 보석의 가치를 출력에         합산한다. 

---

3.  풀이 코드

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

using namespace std;

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); setvbuf(stdout, nullptr, _IOFBF,BUFSIZ)

int main()
{
	fastio;

	int N, K;
	cin >> N >> K;

	vector<pair<int, int>> jewel;	// 보석 정보 배열
	vector<int> backSize;			// 가방 사이즈 배열

	// 보석 정보
	for(int i = 0; i < N; i++)
	{
		int M, V;
		cin >> M >> V;

		jewel.push_back({ M, V });
	}

	// 사이즈 작은 순으로 정렬
	sort(jewel.begin(), jewel.end());	

	// 가방 사이즈
	for(int i = 0; i < K; i++)
	{
		int temp;
		cin >> temp;

		backSize.push_back(temp);
	}

	// 사이즈 작은 순으로 정렬
	sort(backSize.begin(), backSize.end());


	long long answer = 0;
	int index = 0;
	priority_queue<int> candidate;

	// 가방 갯수만큼
	for(int i = 0; i < K; i++)
	{
		while (index < N && jewel[index].first <= backSize[i])
		{
			candidate.push(jewel[index].second);
			index++;
		}

		if (candidate.empty() == false)
		{
			answer += candidate.top();
			candidate.pop();
		}
	}

	cout << answer;

	return 0;
}

---

4. 결과 및 회고

사용할 구조의 추가, 삭제 등의 작동 방법을 한번 더 생각하게 만든 문제.

조건이 쉬워도 구조를 잘못쓰면 어려워질 수 있다.