[BOJ / 그리디] 1202 보석 도둑

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

1202번: 보석 도둑

 

1202 보석 도둑

알고리즘 : 정렬/그리디/우선순위큐

기본적인 틀은 냅색 문제로 보이지만 가방이 여러개인 점과 한 가방안에 보석 하나만 넣을 수 있다는 점에서 차이가 있습니다. 간단히 생각해보면 우선순위큐에 모든 보석을 넣어 가장 좋은 것을 고르려 할 수 있지만, 그러면 간단한 케이스에서도 정해가 나오지 않습니다. 가방과 보석을 크기순으로 정렬하고 가방을 순서대로 순회하면서 해당 순번의 가방크기보다 작거나 같은 모든 보석을 우선순위 큐에 넣어서 가장 큰 가치의 보석만을 정답에 추가한다면 정답을 받을 수 있습니다.

 

 

 

< CODE >

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

using namespace std;

#define MAX 300005
typedef long long int ll;

struct forQ
{
	ll m;
	ll v;
};

forQ jewel[MAX];
ll C[MAX];

ll result = 0;

priority_queue<forQ> pq;

bool operator<(const forQ & a, const forQ & b)
{
	return a.v < b.v;
}

bool cmp(const forQ & a, const forQ & b)
{
	return a.m < b.m;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n,k;
	int mSize = 0;
	
	cin >> n >> k;
	
	for(int i = 0; i < n; i++)
		cin >> jewel[i].m >> jewel[i].v;
	
	for(int i = 0; i < k; i++)
	{
		cin >> C[i];
	}
	
	sort(C, C + k);
	sort(jewel, jewel + n,cmp);
	
	int cIdx = 0;
	int jIdx = 0;
	
	while(cIdx < k)
	{
		while(jIdx < n && C[cIdx] >= jewel[jIdx].m)
		{
			pq.push(jewel[jIdx]);
			jIdx++;
		}
		
		cIdx++;
		
		if(pq.empty())
			continue;			
		
		forQ temp = pq.top();
		result += temp.v;
		
		pq.pop();		
	}
	
	cout << result << '\n';
	
	return 0;
}

시간 : 172ms

 

태그 : #백준 #BOJ 1202 #BOJ 보석 도둑 #알고리즘