BOJ 2258 : 정육점

• 문제 링크 : boj.kr/2258
• 난이도 : G4
• 태그 : 정렬, 그리디

2258번: 정육점

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

bool comp(pii &a, pii &b) {
    if(a.second == b.second) {
        return a.first > b.first;
    }
    return a.second < b.second;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<pii> arr(n);
    for(auto &u : arr) {
        cin >> u.first >> u.second;
    }
    sort(all(arr), comp);

    unsigned int ans = INF + 1;
    unsigned int wsum = 0;
    unsigned int psum = 0;

    for(int i = 0; i < n; i++) {
        wsum += arr[i].first;
        if(i > 0 && arr[i-1].second == arr[i].second) {
            psum += arr[i].second;
        }
        else {
            psum = 0;
        }

        if(wsum >= m) {
            ans = min(ans, psum + arr[i].second);
        }
    }
    if(ans == INF+1) cout << "-1";
    else cout << ans;

    return 0;
}

---

풀이

덤을 받을 수 있다면 모두 받는 것이 이득이다.

따라서 가격을 오름차순으로 정렬한 뒤, 낮은 가격부터 구매했을 때 원하는 양을 구매할 수 있는지 확인해보면 된다.

같은 가격인 덩어리가 여러 개 있을 때가 중요한데, 같은 가격의 덩어리는 서로 덤을 받을 수 없다. 따라서 같은 가격의 덩어리는 무거운 덩어리부터 구매해보며 여러 개를 구매하는 경우를 따져봐야 한다.