[Softeer] 금고털이(lv2) - C++

✏️ 문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

⛔️ 제약조건

1 ≤ N ≤ 106인 정수
1 ≤ W ≤ 104인 정수
1 ≤ Mi, Pi ≤ 104인 정수

🎈 입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

🎈 출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

🎈 입출력 예

• 입력
  100 2
  90 1
  70 2
• 출력
  170

👩‍💻 내 코드

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

using namespace std;

int W, N;
vector<pair<int, int>> items;
int answer;

int main(int argc, char** argv)
{
	cin >> W >> N;

	for(int i = 0; i < N; i++) {
		int M, P;
		cin >> M >> P;
		items.push_back(make_pair(P, M));
	}

	sort(items.begin(), items.end(), greater<>());

	for(auto p: items) {
		int small_w = min(p.second, W);
		W -= small_w;
		answer += (small_w*p.first);
	}
	
	cout << answer;

	return 0;
}

💡 새롭게 배운 것

벡터 내림차순 정렬하는 방법 3가지
1. 표준 라이브러리에 있는 greater<>() 비교 함수 사용
2. 사용자 지정 함수 사용
3. rbegin(), rend() 사용