BOJ - 1202번 보석 도둑(C++)

문제 출처:https://www.acmicpc.net/problem/1202

Level

Gold 2

How to solve

그리디 알고리즘이 생각났다.
가장 작은 가방에서부터 비싼 보석을 넣어준다.

사실 처음에 가방에 보석, 그리고 최대값 구하는 거길래 냅색 알고리즘의 응용인줄 알았는데 가방에 넣을 수 있는 보석이 최대 한개라는 조건을 보고 최선의 해를 찾는 그리디를 하게 됐다.

Code

주의할 점 - long long 변수명 (무게가 1억이 최대기 때문에 더하면 int 범위 넘을 가능성이 있다.)

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


using namespace std;

vector<pair<int,int>> jew;

int main() {
	ios_base::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;
		jew.push_back({ m,v });
	}
	vector<int> bag;
	for (int i = 0; i < K; i++) {
		int L;
		cin >> L;
		bag.push_back(L);
	}
	sort(jew.begin(), jew.end());
	sort(bag.begin(), bag.end());

	int sum = 0;
	priority_queue<int> pq;
	for (int i = 0, j = 0; i < bag.size(); i++) {
		while (j < jew.size() && bag[i] >= jew[j].first) {
			pq.push(jew[j++].second);
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}
	cout << sum << "\n";
	

	return 0;
}

Etc

실패한 코드, 접근은 같은데 틀렸다.
이유는 아직도 모르겠다. 아마 최적의 해를 찾을 때, 먼저 가격 높은 순으로 정렬하고 무게를 신경 안쓰고 코드를 짜서 그런 거 같다.

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

vector<pair<int,int>> jew;

bool comp(pair<int, int> a, pair<int, int> b) {
	if (a.second > b.second) return true;
	return false;
}

bool ch[300001];

int main() {
	ios_base::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;
		jew.push_back({ m,v });
	}
	vector<int> bag;
	for (int i = 0; i < K; i++) {
		int L;
		cin >> L;
		bag.push_back(L);
	}
	sort(jew.begin(), jew.end(), comp);
	sort(bag.begin(), bag.end());

	int jewIdx = 0;
	int sum = 0;
	for (int i = 0; i < bag.size(); i++) {
		if (bag[i] >= jew[jewIdx].first) {
			ch[jewIdx] = true;
			sum += jew[jewIdx++].second;
		}
		else {
			for (int j = jewIdx; j < jew.size(); i++) {
				if (bag[i] >= jew[j].first) {
					ch[j] = true;
					sum += jew[j].second;
					break;
				}
			}
			jewIdx++;
		}
	}

	cout << sum << "\n";
	

	return 0;
}

그래서 다른 사람 코드 풀이를 참고하게 됐다. 접근법이 맞아도 알고리즘을 어떻게 짜고 이용하냐 따라 틀림과 맞음을 결정하는 거 같다. 문제를 더 많이 풀자!