이번 문제는 골드 4 정육점 문제이다.
문제가 굉장히 짧고 간단해 보인다. 차근차근 읽어보자.
고기의 무게와 가격이 주어지고, 은혜가 고기를 사려한다.
고기를 사면 해당 고기보다 싼 고기들은 덤으로 모두 얻을 수 있다.
무게와 가격의 총 합은 INT_MAX를 넘을 수 없다.
우선, 주어진 제한 조건을 보니 int를 사용해도 될 것 같다.
문제를 어떻게 풀어야 할까?
정렬과 그리디
구입한 고기보다 싼 고기는 모두 공짜로 얻을 수 있다니,
대놓고 정렬을 해서 고기를 구입해보라는 말처럼 들린다.
고기를 싼 순서대로 정렬한 뒤 앞에서 부터 선택해보면 되지 않을까?
앞에서 부터 선택하다, 고기의 총 무게가 필요한 무게보다 커질 때
멈추고 해당 위치의 고기 가격을 반환하면 끝이 아닌가?
하지만 단순히 그렇게 풀 수 있으면 골드 4가 아닐 것이다.
어떤 조건을 고려해주어야 할까?
생각해보니, 동일 가격의 고기가 여러개 있을 때를 고려해야 한다.
동일 가격의 고기는 덤으로 못얻으니, 돈을 여러번 내야한다.
그럼 당연히 같은 가격에 더 무거운 고기를 고르는게 이득일 것이다.
따라서 일단 정렬의 2순위를 무게의 내림차순으로 두자.
이제 문제는 같은 가격으로 여러개의 고기를 사는 것 보다,
그 뒤에 나오는 더 비싼 고기를 하나 사는게 더 싸게 치는 경우이다.
예를 들어 2원 고기 3 5 7과 4원 고기 5가 있다고 한다면?
당연히 4원 고기를 사는게 훨씬 쌀 것이다.
위 사항들을 잘 고려해서 코드를 구현하면 아래와 같다.
for (int i = 0; i < num; i++) {
cin >> weight >> cost;
meats.push_back({ cost, weight });
} // 비용 순서로 정렬하도록 하자.
sort(meats.begin(), meats.end(), cmp);
// 싼 비용부터 무게를 더해가면 됨.
ll weight_accum = 0, cost_to_pay = 0, answer = 0;
for (int i = 0; i < meats.size(); i++) {
if (weight_accum < need_weight) {
if (i != 0 && meats[i - 1].first == meats[i].first)
cost_to_pay += meats[i].first;
// 같은 값이면 하나 더 사야함
else
cost_to_pay = meats[i].first;
}
else {
// 고기 무게 합이 넘었을 때
// 비싼 거 하나 사는 게 더 싼지 비교해야함
if ((meats[i - 1].first != meats[i].first) && (cost_to_pay >= meats[i].first))
cost_to_pay = meats[i].first;
// 더 비싼 값일 때, 가격이 더 싼 경우
}
weight_accum += meats[i].second;
}
if (weight_accum < need_weight)
cout << -1;
else
cout << cost_to_pay;