[c++] 백준- 보석도둑 (Greedy)

1. 문제

 

2. 입출력 및 예제

---

3. 문제 해설

 

이 문제를 처음 봤을 때 완전탐색으로는 아주 쉬운 알고리즘으로 풀 수 있겠다는 생각을 했다. 

 

담을 수 있는 무게가 다른 가방이 여러개 있고 보석의 무게와 가치가 여러개 존재한다면 당연히 보석을 최대한의 가치로 가져가는 방법은 담을 수 있는 무게가 가장 작은 가방부터 최대로 채워가는 것이다. 

 

다시 말하면 가장 담을 수 있는 무게가 작은 가방부터 담을 수 있는 보석 중 가장 높은 가치를 가지고 있는 보석을 차례대로 담아가면 되는 것이다. 

 

이것을 완전탐색으로 풀면 for문을 두 번 돌면서 그냥 이 보석이 이 가방에 담을 수 있는 것인지 아닌지를 판별한다음 담을 수 있다면 담을 수 있는 것 중 가장 가치가 큰 것을 선택해 답에 포함시켜주고 선택된 것을 제외시켜주면 되는 것이었다. 

 

그러나 for문을 두 번 돌면 가방의 개수와 보석의 개수 제한은 최대가 300000이기 떄문에 최악의 경우 90000000000번의 연산을 수행해야되서 시간 복잡도를 만족시켜주지 못할 거 같았다. 

 

그러면 어떻게 해야할까를 고민하다가 시간 복잡도를 줄이는 대표적인 방법들에 대한 것을 생각해봤다. 이 문제의 해법을 자세히 생각하다가 항상 정렬을 해야한다는 포인트에 집중했다. 또한 시간복잡도를 만족하려면 O(N)이나 O(NlogN)의 알고리즘이 필요했는데 정렬을 빨리 수행해줄 수 있는 자료구조 중  priority queue를 이용해보기로 했다. 

 

생각은 되게 간단했다. 

 

1. 모든 보석과 가방을 입력받아준 후 보석은 무게 오름차순으로 가방도 담을 수 있는 무게 오름차순으로 정렬해준다.
2. 가방을 기준으로 비교한다. 만약 가방에 이 보석이 들어갈 수 있다면 그 보석의 가치를 priority queue안에 넣어준다.  
3. 한 번 비교한 보석은 다시 비교하지 않는다. 이미 가방을 오름차순으로 정렬했기 때문에 한 번 pq안에 들어가 있는 보석은 다음 가방에도 들어갈 수 있기 때문이다. 
4. priority_queue는 기본적으로 내림차순으로 정렬된다. 따라서 top()에 있는 원소가 현재 가방에 들어갈 수 있는 보석 중 최대 무게를 갖는 보석이다. 따라서 이 보석의 가치를 답에 더해준 후 진행한다. 
5. 모든 가방에 대해 위의 과정을 진행하면 답이 나온다. 

 

4. 코드

#pragma warning (disable :4996)

/*
	입력
	보석 N개
	보석은 M과 V를 가지고 있다. 
	가방을 K개 가지고 있고 가방에 담을 수 있는 최대 무겐 C다. 보석의 최대 가격
	knapsack 문제 - DP
	배열을 선언한다. 
	가로는 물건의 개수 
	세로는 물건의 무개에 해당한다. 

	각 물건의 개수에 대해 무게가 한계 무게까지 증가할 때 현재 무게에 대해 넣을 수 있는 가장 높은 가치를 부분 최적해로 놓는다. 

	1. 현재 고려하는 물건의 무게가 현재 고려하는 무게보다 큰 경우
		- 넣을 수 없다. 
		value[i][j] = value[i-1][j]
	2. 현재 고려하는 물건의 무게가 현재 고려하는 무게보다 작아 배낭에 물건을 넣을 수 있는 경우?
		- 넣을 수 있다. 
		1. 안넣는 경우가 더 나은 경우
		value[i][j] = value[i-1][j]
		2. 넣는 것이 더 나은 경우
		value[i][j] = val + value[i-1][j-wi];
		---
		value[i][j] = max(value[i-1][j] , val + value[i-1][j-wi])


		풀이
		-> 가방을 가능한 무게 순으로 asc 정렬
		-> 보석 무게에 asc 정렬
		-> 가능한 보석을 
*/
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long 
int N, K;
vector<pair<int, int>> jewel;
vector<int> bp;
priority_queue<int> pq;
ll ans;
bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.first < b.first) return true;
	else return false;
}
void input() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		int weight, val;
		scanf("%d %d", &weight, &val);
		jewel.push_back({ weight, val });
	}
	for (int j = 0; j < K; j++) {
		int wei;
		scanf("%d", &wei);
		bp.push_back(wei);
	}
}
void sol() {
	sort(jewel.begin(), jewel.end(), cmp);
	sort(bp.begin(), bp.end()); // 두개 정렬
	
	int i = 0;
	for (int j = 0; j < K; j++) {
		while (i < jewel.size() && jewel[i].first <= bp[j] ) {
			pq.push(jewel[i].second);
			i++;
		}

		if (pq.empty()) continue;
		else { 
			ans += pq.top();
			pq.pop();
		}
	}
	printf("%lld\n", ans);
}
int main() {
	input();
	sol();

	return 0;
}

만약 이 문제와 같이 greedy알고리즘을 사용해야하는 문제라면 priority_queue사용을 우선적으로 고려해봐야겠다.