[백준 4716] 풍선

그리디 연습

1. 풀이

사실 직접 풍선을 최적으로 배분하는 과정을 여러 시뮬레이션을 해보면 왼쪽 최솟값인 애들에게 전부 나누어주고, 오른쪽 최솟값인 애들에 전부 나누어주고, 다음에 남은 풍선들로 왼쪽에 있는 애들과 오른쪽에 있는 풍선을 섞어서 나누어주게 된다.

그럼 잘 생각을 해보면 왼쪽, 오른쪽 최솟값으로 풍선을 나누어주는 것은 언제나 최적이다. 그러면 코스트에 영향을 주는 것은 왼쪽과 오른쪽으 풍선을 섞어서 주는 경우에서 코스트가 차이가 나게 되므로 이 상황에서 최적으로 배분을 할 수 있다면 최적이 될 것이다.

왼쪽과 오른쪽을 섞는 상황에서는 왼쪽과 오른쪽의 값이 덜 차이나는 것이 무조건 이득이다. 잘 정렬해서 나누어주기만 하면 된다.

2.소스 코드

#include <bits/stdc++.h>


using namespace std;


struct Boo {
    int k, l, r;
};


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


    while (true) {
        int n, a, b; cin >> n >> a >> b;
        if (n == 0 && a == 0 && b == 0) break;
        vector<Boo> arr(n);
        int sumA = 0, sumB = 0;
        for (int i = 0; i < n; i++)
            cin >> arr[i].k >> arr[i].l >> arr[i].r;


        sort(arr.begin(), arr.end(), [](Boo& a, Boo& b) -> bool {
            int da = abs(a.l - a.r);
            int db = abs(b.l - b.r);
            if (da != db) return da > db;
            return a.k > b.k;
            });


        int ans = 0;
        for (Boo& w : arr) {
            if (w.l <= w.r) {
                int cnt = min(w.k, a);
                ans += cnt * w.l;
                a -= cnt, w.k -= cnt;
                
                if (w.k > 0) {
                    cnt = min(w.k, b);
                    ans += cnt * w.r;
                    b -= cnt, w.k -= cnt;
                }
            }
            else{
                int cnt = min(w.k, b);
                ans += cnt * w.r;
                b -= cnt, w.k -= cnt;


                if (w.k > 0) {
                    cnt = min(w.k, a);
                    ans += cnt * w.l;
                    a -= cnt, w.k -= cnt;
                }
            }
        }


        cout << ans << "\n";
    }


    return 0;
}