Softeer Lv.2 금고털이

Softeer Lv2. 금고털이

간단한 구현문제

다른문제들에서 하도 쎄게 데여서 다른 숨겨진게 있을까 했는데

가장 기본적인 구현문제였다

https://softeer.ai/practice/6288

1. 문제

---

간단 설명

W Kg까지 담을 수 있는 가방에, 가장 많은 보석을 챙기는 문제

0/1 가방 문제가 아니라, 분할 가능한 가방문제이므로, 가치가 높은순으로 담는다

2. 문제 분석

---

필요변수

가방크기 int W, 귀금속의 종류 int N

보석의 무게 M과, 무게당 가격 P.

이를 담을 수 있는 구조체 또는 벡터 이용

vector<pair<int, int>> item

주의점

• 가치가 높은 순으로 훔쳐야하므로, 구조체의 정렬이 필요하다

알고리즘

1. W, N을 입력받는다
2. N개의 보석의 정보를 입력받아 item 벡터에 저장한다
3. item 벡터를 무게당 가치 순으로 정렬한다
4. 남은 가방의 무게를 확인하면서, 무게당 가치가 높은 물건부터 가방에 담는다
    4-1. 남은 무게보다 현재 아이템의 전체 무게가 작다면, 통째로 넣는다
    4-2. 남은 무게보다 현재 아이템의 무게보다 크다면, 남은 무게만큼 잘라서 넣는다.
        - 이후 더이상 물건을 살펴보지 않아도 된다. 가방이 꽉찼으므로
5. 전체 가방의 가치를 출력한다

3. 소스코드

---

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

using namespace std;

int W, N;
vector< pair<int, int> > item;

bool compare(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() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> W >> N;
	for (int i = 0; i < N; i++) {
		int m, p;
		cin >> m >> p;
		item.push_back(make_pair(m, p));
	}

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


	int total_value = 0; 
	int left_weight = W;
	int i = 0;
	while(left_weight>0){
		if (left_weight > item[i].first) {
			left_weight -= item[i].first;
			total_value += item[i].second * item[i].first;
			i++;
		}
		else {
			total_value += item[i].second * left_weight;
			left_weight = 0;
			break;
		}
	}

	cout << total_value;

	return 0;
}