https://www.acmicpc.net/problem/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;
}
'c++ > Baekjoon Online' 카테고리의 다른 글
백준 11967 : 불켜기 C++ (0) | 2021.09.12 |
---|---|
백준 6198 : 옥상 정원 c++ (monotone stack) (0) | 2021.07.01 |
백준 1461 : 도서관 C++ (0) | 2021.06.27 |
백준 8980 : 택배 C++ (0) | 2021.06.27 |
백준 1507 : 궁금한 민호 C++ (0) | 2021.06.27 |