(cpp) Softeer ‘금고털이’ - 그리디

03 Oct 2022 on Programming Languages

Softeer ‘금고털이’ - 그리디

---

문제

풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>

using namespace std;
int w,n,m,p;
vector<pair<int,int>> mp;

bool cmp(const pair<int,int>&a, const pair<int,int>&b){
	if(a.second == b.second){return a.first < b.first;}
	return a.second > b.second;
}
int main(int argc, char** argv)
{
	//배낭에 담을 수 있는 최대무게 w
	//금속 종류 n개, 금속의 무게m, 무게 m당 가격p
	//금속 쪼갤 수 있음.
	//가벼운 금속이면서 비싸야 좋음.
	//단위무게당 가격이 큰 금속(A)으로 먼저 채우기
	//최대용량 w <= A_w : A로만 다 채우면 됨 w=0; val = w*A_val
	//최대용량 w > A : A로 다 채우고 다음 순위로 넘어가기,w=w-A; val = A_w * A_val
	//w=w-A <= B : B로만 다 채우면 됨
	//w=w-A > B : B로 다 채우고 다음 순위로 넘어가기, w=w-A-B;
	//w==0 될 때까지 반복

	cin >> w >> n;
	int ret=n;
	while(ret--){
		cin>> m >> p;
		mp.push_back(make_pair(m,p));
	}

	sort(mp.begin(),mp.end(),cmp);
	//for(int i=0;i<n;i++){printf("%d %d\n",mp[i].first,mp[i].second);}
	int i=0;
	int val =0;

	for(int i=0; i<n; i++){
		if(w <= mp[i].first){
			val = val + w*mp[i].second;
			w=0;}
		
		else if(w>mp[i].first){
			val=val+mp[i].first*mp[i].second;
			w=w-mp[i].first;
		}
	}
	printf("%d",val);

}