문제 출처

1. 문제설명

  • 보석점에 총 N개의 보석이 있다.
  • 각 보석은 무게 M, 가격 V를 가진다.
  • 상덕이는 가방 K를 가지고 있고, 최대 C의 무게를 담을 수 있다.
    • 가방에는 한 개의 보석만 넣을 수 있다.
  • 훔칠 수 있는 보석의 최대 가격을 구하라!



2. 알고리즘 설계

  • 그리디 문제이다.
  • 가방이 한정되어 있으므로, 가방의 가성비(?)를 따져 훔치면 된다.



3. 로직

  • 무게 순으로 정렬하되, 무게가 같다면 가치순으로 정렬한다.
  • 가방 또한 담을 수 있는 무게가 큰 순으로 정렬한다.
  • 사용할 가방의 수가 여유가 있으면서, 무게를 넘지 않으면,
    • 우선순위 큐에 정렬된 가격을 넣는다.
    • 우선순위 큐가 비어있지 않다면, top의 원소를 더해주면 된다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

typedef struct {
	int m, v;
}Jwe;

bool compare(const Jwe& a, const Jwe& b) {
	if (a.m == b.m) return a.v < b.v;
	return a.m < b.m;
}

int bag[300000];
Jwe j[300000];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int m, v;
		cin >> m >> v;
		j[i] = { m,v };
	}

	for (int i = 0; i < k; i++)
		cin >> bag[i];

	sort(j, j + n, compare);
	sort(bag, bag + k);

	priority_queue<int> pq;
	int idx = 0;
	long long res = 0;
	for (int i = 0; i < k; i++) {
		while (idx < n && j[idx].m <= bag[i])
			pq.push(j[idx++].v);

		if (!pq.empty()) { 
			res += (long long)pq.top();
			pq.pop();
		}
	}

	cout << res;
	return 0;
}



5. 소감

  • 이 문제는 최대치를 계속해서 더할 경우,
  • int 범위를 넘어서기 때문에 반드시 자료형을 신경써야 한다.
  • long long 타입을 사용하였다.