[C++] 앱 (백준 7579번)

https://www.acmicpc.net/problem/7579

 

0-1 냅색 문제이다. 기본적인 0-1 냅색에 대한 내용은 이 글의 평범한 배낭 문제 부분에 잘 정리되어 있다. 

기본적인 0-1 냅색에서의 dp 배열은 다음과 같다.

dp[i][j] : 가방의 무게가 i이고, j번째 물건까지 살펴봤을 때, 가방에 담을 수 있는 최대 가치

 

그래서 다시 이 문제로 돌아오면... 이 문제는 크게 두 가지 방법으로 해결할 수 있다.

1. 2차원 dp 배열로 해결하기

dp[i][j] : i만큼의 비용으로 j번째 앱까지 확인했을 때, 얻을 수 있는 최대 메모리

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

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

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

    vector<int> mem(n + 1);
    for (int i = 1; i < n + 1; i++) cin >> mem[i];

    vector<int> c(n + 1);
    for (int i = 1; i < n + 1; i++) cin >> c[i];

    vector<vector<int>> dp(10001, vector<int>(n + 1, 0));

    for (int i = 0; i < 10001; i++) { // i만큼의 비용으로
        for (int j = 1; j < n + 1; j++) { // j번째 앱까지 확인
            dp[i][j] = dp[i][j - 1]; // j번째 앱을 사용하지 않은 경우
            if (i - c[j] >= 0) dp[i][j] = max(dp[i][j], dp[i - c[j]][j - 1] + mem[j]); // j번째 앱을 선택하는 게 더 이득이면 업데이트
        }
    }

    for (int i = 0; i < 10001; i++) {
        if (dp[i][n] >= m) {
            cout << i << '\n';
            return 0;
        }
    }
}

(AC)

2. 1차원 dp 배열로 해결하기

dp[c] : c만큼의 비용으로 얻을 수 있는 최대 메모리

 

어떻게 일차원으로 줄일 수 있는 걸까?

일단 1번 방법을 읽으면 알 수 있듯이 dp[i][j]를 업데이트 할 때 dp[*][j - 1]만 확인하면 된다. 즉, 이전 것들은 필요가 없다.

 

그런데 값을 갱신시킬 때 참고하는 값이 무조건 자기 자신보다 앞의 값이기 때문에, 이전 (j-1) 배열과 현재 (j) 배열을 따로 두면서 스왑하고 할 필요없이 뒤에서부터 갱신해주면 되는 것이다. 

 

다시 말해, 앱을 하나씩 보면서 dp 배열을 쭉 업데이트 시키되, dp 배열을 뒤에서부터 업데이트 시키면 앱을 무조건 한 번씩만 사용하는 것이 보장된다. 

왜 그런지는 그림을 보면 더 쉽게 이해할 수 있다. 

 

따라서 이런 dp를 풀 때는 뒤에서부터 보면서 갱신해주면 굳이 2차원 배열을 두거나 1차원 배열을 2개 둘 필요없이 1차원 배열 하나만으로도 해결이 가능한 것이다.

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

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

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

    vector<int> mem(n);
    for (int i = 0; i < n; i++) cin >> mem[i];

    vector<int> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];

    vector<int> dp(10001, 0);

    for (int i = 0; i < n; i++) { // i번째 앱 확인
        for (int j = 10000; j >= 0; j--) { // j만큼의 비용 (역순으로 업데이트!)
            if (j - c[i] >= 0) dp[j] = max(dp[j], dp[j - c[i]] + mem[i]);
        }
    }

    for (int i = 0; i < 10001; i++) {
        if (dp[i] >= m) {
            cout << i << '\n';
            return 0;
        }
    }
}

(AC)