JArchive 프로그래밍 일기

금고털이 문제 링크 

리뷰 

가격이 가장 비싼 것 부터 담아야 한다. 

따라서 '가격' 을 우선으로 정렬해야 한다. 

담았을 때마다 가격은 더해주되, 바구니 무게 w는 무게만큼 빼준다. 

바구니에 담을 수 있는 무게 w가 0이 되면 종료시킨다. 

맞았습니다 코드 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int w, n, a, b;
int answer;
vector<pair<int,int>> v;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> w >> n;
  for(int i = 0; i < n; i++){
    cin >> a >> b; // {무게, 가격}
    v.push_back({b, a}); // {가격, 무게}
  }

  sort(v.begin(), v.end(), greater<>());
  for(auto a : v){
    int small_weight = min(w, a.second);
    answer += (small_weight * a.first);
    w -= small_weight;
    if(w == 0) break;
  }
  cout << answer;
  return 0;
}

제출기록