[백준] 7579번 - 앱 [Java][C++]

문제 링크

---

1. 문제 풀이

활성화된 앱들이 주어져 있고 각 앱은 비활성화 했을 때, 비용 $c$ 와 확보할 수 있는 메모리 $m$ 을 가지고 있다. 이때 $M$ 이상의 메모리를 확보할 때 최소 비용을 알아내야 하는 문제다. 이는 비용을 무게, 확보할 수 있는 메모리를 가치로 간주하는 0／1 배낭 문제로 해결할 수 있다. 각 앱을 비활성화하느냐 마느냐를 0／1 배낭 문제로 쭉 계산한 후 비용이 $0$ 일 때 확보할 수 있는 메모리부터 쭉 탐색해서 확보할 수 있는 메모리가 $M$ 이상이면 종료하면 된다.

비활성화 했을 때 비용이 $0$ 일 수 있음에 주의해야 한다.

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] mArr = new int[1 + N];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            mArr[i] = Integer.parseInt(st.nextToken());
        }

        int[] cArr = new int[1 + N];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            sum += cArr[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[1 + N][1 + sum];
        for (int i = 1; i <= N; i++) {
            int m = mArr[i];
            int c = cArr[i];

            for (int j = 0; j <= sum; j++) {
                if (j < c) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - c] + m, dp[i - 1][j]);
                }
            }
        }

        for (int j = 0; j <= sum; j++) {
            if (dp[N][j] >= M) {
                System.out.println(j);
                return;
            }
        }
    }
}

2. Bottom-Up 1차원 dp [Java]

0／1 배낭 문제라서 1차원 dp는 역방향 탐색으로 진행했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] mArr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            mArr[i] = Integer.parseInt(st.nextToken());
        }

        int[] cArr = new int[N];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sum += cArr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[1 + sum];
        for (int i = 0; i < N; i++) {
            int m = mArr[i];
            int c = cArr[i];

            for (int j = sum; j >= c; j--) {
                dp[j] = Math.max(dp[j - c] + m, dp[j]);
            }
        }

        for (int j = 0; j <= sum; j++) {
            if (dp[j] >= M) {
                System.out.println(j);
                return;
            }
        }
    }
}

3. Bottom-Up 2차원 dp [C++]

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

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

    int n, m;
    cin >> n >> m;

    vector<int> ma(n);
    for (int& x : ma) cin >> x;

    vector<int> ca(n);
    for (int& x : ca) cin >> x;

    int sum = 0;
    for (int x : ca) sum += x;

    vector<vector<int>> dp(1 + n, vector<int>(1 + sum));
    for (int i = 1; i <= n; i++) {
        int mi = ma[i - 1];
        int ci = ca[i - 1];

        for (int j = 0; j <= sum; j++) {
            if (j < ci) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j - ci] + mi, dp[i - 1][j]);
            }
        }
    }

    for (int j = 0; j <= sum; j++) {
        if (dp[n][j] >= m) {
            cout << j;
            return 0;
        }
    }
}

4. Bottom-Up 1차원 dp [C++]

0／1 배낭 문제라서 1차원 dp는 역방향 탐색으로 진행했다.

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

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

    int n, m;
    cin >> n >> m;

    vector<int> ma(n);
    for (int& x : ma) cin >> x;

    vector<int> ca(n);
    for (int& x : ca) cin >> x;

    int sum = 0;
    for (int x : ca) sum += x;

    vector<int> dp(1 + sum);
    for (int i = 0; i < n; i++) {
        int mi = ma[i];
        int ci = ca[i];

        for (int j = sum; j >= ci; j--) {
            dp[j] = max(dp[j - ci] + mi, dp[j]);
        }
    }

    for (int j = 0; j <= sum; j++) {
        if (dp[j] >= m) {
            cout << j;
            return 0;
        }
    }
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	132 ms	18816 KB	1361 B

2. Bottom-Up 1차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	120 ms	14444 KB	1200 B

3. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	6092 KB	819 B

4. Bottom-Up 1차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2180 KB	657 B

---