Softeer : 금고털이 _ C++

https://softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

 

회고

이번에 현대 모비스 코딩테스트를 보게 되어서 접하게 된 새로운 알고리즘 사이트였다.

Softeer 는 현대자동차 그룹에서 제공하는 알고리즘 문제 사이트? 인것같다.

현대 모비스의 경우 결과 발표와 시험 일정이 빠듯하게 잡혀서 해당 사이트에서 문제는 별로 풀어보지도 못하고 시험을 치르게 될 것 같아 걱정이 조금은 되지만 경험 쌓는 셈 치고 당일날 열심히 풀어봐야겠다.

 

아무튼, 문제 풀면서 느낀 점으로 돌아가보도록 하겠다.

이 문제를 풀기 전에 냅색 문제를 풀었어서 별 생각도 없이 dp로 풀면 되나?! 싶었는데 보석의 최대 개수가 너무 커서 그렇게 접근하는것이 아님을 깨달았다.

다시 생각해보니 가격 순으로 정렬을 해 주고 그리디 하게 최대 무게까지 가져가면 되는 쉬운 문제였다.

 

코드

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

using namespace std;

struct JEWEL {
	int weight, price;
};

bool cmp(JEWEL a, JEWEL b) {
	if (a.price == b.price) {
		return a.weight < b.weight;
	}
	return a.price > b.price;
}

int main(int argc, char** argv)
{
	int W, N;
	cin >> W >> N;
	vector<JEWEL> bag;

	int w, p;
	for (int i = 0; i < N; i++) {
		cin >> w >> p;
		bag.push_back({ w,p });
	}

	sort(bag.begin(), bag.end(), cmp);

	int res = 0;
	int idx = 0;
	int total_weight = 0;
	while (total_weight <= W) {
		if (idx >= N) break;
		int cur_weight = bag[idx].weight;
		int cur_price = bag[idx].price;
		if (cur_weight > W && idx == 0) {
			res = W * cur_price;
			break;
		}
		if ((total_weight + cur_weight) > W) {
			cur_weight = W - total_weight;
			res += cur_weight * cur_price;
			break;
		}

		total_weight += cur_weight;
		res += cur_weight * cur_price;
		idx++;
	}
	cout << res;
	return 0;
}