[C++] 백준(BOJ) - 1202 : 보석 도둑

29 Feb 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 1202 : 보석 도둑(링크)

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

알고리즘

1. 그리디
2. 우선순위 큐

풀이

1. 넣을 수 있는 보석(보석의 무게가 가방의 무게보다 작거나 같은 경우)들 중에 가장 값비싼 보석을 Push
2. Priority_queue (max Heap) 안에 미리 보석의 값어치가 큰대로 집어 넣어 두면 보석을 넣을 다음 가방으로 넘어갈 때, 재탐색 시 pq의 top만 확인하면 된다.

코드

// BOJ-1202 : 보석 도둑
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k, m, v;
ll res;
vector<pair<ll, ll>> vec;
vector<ll> vec2;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;

	priority_queue<ll> pq;

	for (int i = 0; i < n; i++)
	{
		cin >> m >> v;
		vec.push_back({m, v});
	}

	for (int i = 0; i < k; i++)
	{
		int a;
		cin >> a;
		vec2.push_back(a);
	}

	sort(vec.begin(), vec.end());
	sort(vec2.begin(), vec2.end());

	int i = 0; // 보석무게, 가격 인덱스
	for (int j = 0; j < k; j++)
	{
		while (i < n && vec[i].first <= vec2[j]) pq.push(vec[i++].second); // pq 삽입 후 다음 보석으로 인덱스 넘어가기

		if (pq.size())
		{
			res += pq.top();
			pq.pop();
		}
	}

	cout << res << '\n';

	return 0;
}

평가

• 할 수 있는 방법을 다 진행한 후 효율적으로 답을 탐색해가는 과정 => 최적해 탐색