[ 백준 / 1202 ] 보석 도둑 (C++)

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

 

난이도 : 골드 2 
알고리즘 유형 : 그리디, 우선순위 큐
풀이 시간 : 1시간 25분 

문제 풀이 

각 보석은 무게 $M_i$와 가격 $V_i$를 가지고 있고, 상근이는 무게가 $C_i$인 가방을 K개 가지고 있고, 이 가방에는 한 개의 보석만 담을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구해보자.

 

문제의 조건을 확인해보면 보석의 총 개수와 가방의 개수가 $1 ≤ N, K ≤ 300000$ 이고, 보석의 정보는 $1 ≤ M_i, V_i ≤ 1000000$이다. 

 

먼저 베낭 문제처럼 각 보석의 개수와 가방의 총 개수에 대한 완전 탐색을 진행하게 되면 $300000 * 300000$으로 무조건 시간초과가 난다. 따라서, 우리는 그리디 알고리즘을 사용해서 최적의 경우에 대해 판단해야한다.

또한, 만약 보석이 총 $300000$ 개가 있고, 각 보석의 가치가 모두 $1000000$이라면, 이는 int형의 범위를 충분히 넘어가게 된다. 따라서, int 형 대신 long long int 형을 사용하여 문제를 풀어나가야 한다.

 

문제를 풀이하는 데 핵심은 정렬과 우선순위 큐 이다.우리는 그리디하게 문제를 해결해야 하기 때문에, 먼저 보석의 크기가 큰 순서대로 순회를 하며 크기가 큰 가방 순서대로 담을 것이다. 여기서 조건문을 사용한다면, (조건 1)사용할 수 있는 가방이 있고, 보석의 무게가 가방의 제한 무게보다 낮거나 같은 경우에 가방에 보석을 담을 것이다.

 

만약, (조건 1)을 만족하지 않는다면,우선순위 큐를 사용할 것이다. 

우선순위 큐에는 <보석의 값이 낮은 순, 값이 같을 경우, 가방의 무게가 낮은 순> 으로 우선순위를 정해서 담을 것이다. 이후 (조건 1)을 만족하지 않는 경우, 우선순위큐의 top과 현재 보석을 비교할 것이다.

 

만약 보석의 값이 우선순위 큐의 가격보다 크고, 가방에 넣을 수 있다면 현재 우선순위 큐의 맨 앞 값을 빼주고, 새로운 보석값을 더해준다. 여기서 가방의 사이즈는 무게가 큰 순으로 설정하였기 때문에 신경쓰지 않아도 된다.

 

이렇게 그리디 알고리즘 로직을 작성한다면, 시간복잡도 $O(n)$ 내에 문제를 해결할 수 있다.

 

코드

/*
각 보석은 무게 m과 가격 v를 갖고 있다.
상근이는 가방을 k개 갖고있다.
각 가방에 담을 수 있는 최대 무게는 c이다.
가방에는 최대 한 개의 보석만 넣을 수 있다.
훔칠 수 있는 보석의 최대 가격은 ?

풀이 : 
2중 for문을 돌아야 하기 때문에 시간초과 -> 냅색 불가능
그렇다면 ,, n개 줄 안에 무조건 끝내야한다.

heapq로 가방을 관리하자 ?
heapq로는 무조건 가방을 넣을 수 있도록 해야하기 때문에, 들어갈 자리가 있는지 확인하기

*/

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
#define lli long long int

using namespace std;

lli n, k;
lli c;

bool cmp(pair<lli, lli> a, pair<lli, lli> b) {
	if (a.first == b.first)
		return a.second < b.second;
	return a.first < b.first;
}

struct cmp2 {
	bool operator()(pair<lli, lli> a, pair<lli, lli> b) {
		if (a.second == b.second)
			return a.first < b.first;
		return a.second > b.second;
	}
};


int main() {
	INIT;
	cin >> n >> k;
	vector<pair<lli, lli>> jewelry(n);
	vector<lli> bagpack(k);
	for (int i = 0; i < n; i++)
		cin >> jewelry[i].first >> jewelry[i].second;
	for (int i = 0; i < k; i++)
		cin >> bagpack[i];
	priority_queue<pair<lli, lli>, vector<pair<lli, lli>>, cmp2> pq;

	sort(bagpack.begin(), bagpack.end());
	sort(jewelry.begin(), jewelry.end(), cmp);

	lli ans = 0;
	// 일단 다 넣고 시작하기
	// 만약 넣을 자리 없다면, (보석의 값이 낮은 순, 값이 같을 경우, 가방의 무게가 낮은 순)으로 정렬해서 채워넣기
	for (int i = n - 1; i > -1; i--) {
		if (!bagpack.empty() && bagpack.back() >= jewelry[i].first) {
			ans += jewelry[i].second;
			pq.push({ bagpack.back(), jewelry[i].second });
			bagpack.pop_back();
		}
		// 다 차 있는 경우, pq에서 찾아내기
		else {
			if (!pq.empty() && pq.top().first > jewelry[i].first) {
				if (pq.top().second < jewelry[i].second) {
					int bag = pq.top().first;
					ans += jewelry[i].second - pq.top().second;
					pq.pop();
					pq.push({ bag, jewelry[i].second });
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

배운 점 

본 문제에서 변수의 타입을 신경쓰지 않아 문제를 푸는 데 매우 긴 시간이 걸렸다. C++의 경우, 변수의 범위를 항상 신경쓰고 & 주소공간을 한 번 더 확인하며 문제를 풀어나가야겠다.