BOJ 17533

 

존재한다면 -> 존재하지 않는다면

땅따먹기를 하다 발견한 문제이다. 처음에는 P5로 기여돼 있어서 만만하게 보고 풀기 시작했지만 정말 어려운 문제였다. 그리디한 접근이 가장 직관적으로 떠오르지만 그건 함정이었고, 실제로는 빈 수조가 있을 경우에 답이 완전히 달라지기 때문에 그리디와 배낭 문제를 결합해서 풀어야 한다. 자세한 풀이는 위 슬라이드를 참고하면 된다. 

 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

constexpr ll INF = 1LL << 61;

void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int main() {
    init();

    ll n, emp = 0, m = 0;
    cin >> n;
    vector<pll> v;
    for (ll x, y, i = 0; i < n; i++) {
        cin >> x >> y;
        m += x;
        if (!y) {
            emp++;
        } else {
            v.emplace_back(x, y);
        }
    }

    if (!m) {
        cout << 0;
        return 0;
    }

    ranges::sort(v, [&](pll x, pll y) {
        return x.first - x.second < y.first - y.second;
    });
    ll ans = INF;
    vector<ll> dp(emp + 1, INF);
    dp[0] = 0;
    for (auto [x, y] : v) {
        ll mx = max(0LL, x - y + 1);
        for (ll i = emp; i >= 0; i--) {
            ll tmp = min(i, x);
            dp[i] = min(dp[i], dp[i - tmp] + min(mx, tmp));
        }
    }

    for (ll i = 0; i <= emp; i++) {
        ans = min(ans, emp - i + dp[i]);
    }
    if (!emp) {
        ans += max(0LL, v.front().first - v.front().second + 1);
        ans += max(0LL, v.back().second - v.back().first - 1);
    }
    for (auto [x, y] : v) {
        ans += x + min(x, y - 1);
    }
    cout << ans - emp;
    return 0;
}