백준 2258 : 정육점 c++

https://www.acmicpc.net/problem/2258

2258번: 정육점

 

고려해야될 점

 

1. 같은 가격인 애들이 여러개 주어졌을때를 꼭 생각해야 된다.

ex) 3원짜리 고기 3g 5g vs 5원짜리 고기 10g 

위의 경우의 5원짜리를 골라야 된다.

 

이것만 신경쓰면 쉽다

 

2. 가격이 싼순, 동일할때는 무게 무거운 순으로 정렬

 

3. 아직 합친무게가 원하는 정도가 아닌데, 동일 무게가 있으면 추가로 구매해야된다!!

if (before == meat[i].second)
{
sum_price += meat[i].second;
}
else
{
before = sum_price = meat[i].second;
}

 

4. 그냥 더 비싼거 한개사는게 더 싸면, 정답 수정

if ((before != meat[i].second) && (sum_price >= meat[i].second))
{
before = sum_price = meat[i].second;
}

 

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

//가격 싼 순
// 같은 가격이면, 무거운거
bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.second == b.second)
		return a.first > b.first;

	return a.second < b.second;
}

int n,need;
int answer = 2147483647;
vector<pair<int, int> > meat;


int main()
{
	cin >> n >> need;
	for (int i = 0; i < n; i++)
	{
		int price;
		int weight;
		cin >> weight >> price;
		meat.push_back(make_pair(weight, price));
	}

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

	//고기를 사면 그 아래 값은 전부 덤

	int sum_weight = 0;
	int sum_price = 0;
	int before = -1;
	for (int i = 0; i < meat.size(); i++)
	{
		if (sum_weight < need)
		{
			//동일 가격인놈이 있을때
			
			if (before == meat[i].second)
			{
				sum_price += meat[i].second;
			}
			else
			{
				before = sum_price = meat[i].second;
			}
		}
		else
		{
			//같은 가격 여러개 vs 비싼놈 하나 비교 필요
			if ((before != meat[i].second) && (sum_price >= meat[i].second))
			{
				before = sum_price = meat[i].second;
			}
		}

		sum_weight += meat[i].first;
	}

	if (sum_weight < need)
		cout << -1 << endl;
	else
		cout << sum_price << endl;

	return 0;
}