BOJ 7579 — App

BOJ 7579 — App

Minimize the deactivation cost

App $i$ releases $m_i$ units of memory when deactivated and costs $c_i$. Choose a set of apps whose released memory is at least $M$, minimizing the sum of their costs.

A DP indexed by required memory is too large: $M$ can be much larger than the sum of deactivation costs. The constraints bound each cost by 100 and the number of apps by 100, so the total cost is at most 10,000. Use cost as the DP dimension instead.

DP invariant

Let best[b] be the maximum memory that can be released with total cost at most b. This is an at-most-budget definition; initializing every entry to zero is intentional.

For each app, either keep the best result without it or deactivate it:

Process budgets in descending order so the current app cannot be selected more than once. This also handles a zero-cost app: each budget is updated once for that app. The answer is the smallest budget whose best[b] is at least $M$.

Correctness

After processing the first $i$ apps, best[b] is the largest memory obtainable from a subset of those apps with cost at most $b$. For app $i+1$, every feasible subset either omits it, preserving the previous value, or includes it, adding its memory to a subset of cost at most $b-c_{i+1}$. The recurrence takes the larger of these two cases. Descending iteration reads only states from the previous app layer, so no app is reused. By induction the invariant holds after all apps, and the first budget meeting $M$ is the minimum possible cost.

The time complexity is $O(NC)$ and the space complexity is $O(C)$, where $C=\sum_i c_i$.

C++17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, required_memory;
    cin >> n >> required_memory;

    vector<int> memory(n), cost(n);
    for (int& value : memory) cin >> value;
    for (int& value : cost) cin >> value;

    const int total_cost = accumulate(cost.begin(), cost.end(), 0);
    vector<int> best(total_cost + 1, 0);

    for (int i = 0; i < n; ++i) {
        for (int budget = total_cost; budget >= cost[i]; --budget) {
            best[budget] = max(best[budget], best[budget - cost[i]] + memory[i]);
        }
    }

    for (int budget = 0; budget <= total_cost; ++budget) {
        if (best[budget] >= required_memory) {
            cout << budget << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
}

Source history

Adapted from “백준 7579번 - 앱”, originally published on 2022-04-18 by MINJUN PARK and marked CC BY 4.0. The cost-indexed 0/1-knapsack approach is retained; this version clarifies the at-most-budget invariant and replaces the GNU variable-length array with standard C++17.