[C++] 소프티어 금고털이 [Greedy]

https://softeer.ai/practice/formCodeEditor.do

Softeer

풀이

무게 당 가격이 주어질 때, 가방을 채울 수 있는 최대 가치를 구하는 문제입니다.

 

1단위로 쪼개서 가방을 채울 수 있으므로, 가치가 높은 것부터 최대로 채우는 것이 정답이 됩니다.

 

따라서, 금속 가치에 따라 내림차순 정렬 후 그리디 하게 처리하면 해결할 수 있는 간단한 문제입니다.

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

using namespace std;

int W, N, M, P, ans=0;

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
	return a.second > b.second;
}

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

	cin >> W >> N;
	vector<pair<int, int> > v(N);
	for (int i=0; i<N; i++) {
		cin >> v[i].first >> v[i].second;
	}
	sort(v.begin(), v.end(), cmp);

	for (int i=0; i<v.size(); i++) {
		if (v[i].first >= W){
			ans += W*v[i].second;
			break;
		}
		else{
			W -= v[i].first;
			ans += v[i].first * v[i].second;
		}
	}
	cout << ans << endl;

	return 0;
}