[현대 소프티어] (C++) 금고털이

Greedy 문제이다.

Greedy라 칭하기엔 너무 쉬운 문제였지만 알고리즘만 놓고 본다면 Greedy에 속한다.

보통 자를수 없게 나오는데 자를수 있어서 쉽게 풀었다.

어려움 없이 가치 순 대로 정렬한 후, W를 빼면서 최대 가치를 구하면 된다.

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

using namespace std;

typedef struct jewl {
	int M;
	int P;
} jewl;

bool compare(jewl a, jewl b) {
	return a.P > b.P;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int W, N; cin >> W >> N;

	vector<jewl> arr;

	int a, b;
	for(int i = 0; i < N; i++) {
		cin >> a >> b;

		arr.push_back({a, b});
	}

	sort(arr.begin(), arr.end(), compare);

	int val = 0;
	for(int i = 0; i < N; i++) {
		if(W >= arr[i].M) {
			val += arr[i].M * arr[i].P;
			W -= arr[i].M;
		}
		else {
			val += W * arr[i].P;
			W = 0;
		}

		if(W == 0)
			break;
	}

	cout << val << '\n';

	return 0;
}