백준 7579 앱 (C++)

7579번: 앱

배낭 문제를 응용한 dp 문제이다. 배낭 문제는 최대 무게 내에서 최대 가치를 구하는 문제였던 반면, 이번 문제는 주어진 메모리를 넘겨 최소 비용을 구하는 문제이다. 점화식은 아래와 같다.

dp[앱 번호][비용] = 최대 메모리, 즉 i번째 앱까지 확인했을 때 j 비용에서의 최대 메모리

점화식 자체는 기존 배낭 문제와 같다. 다른 점은 M을 넘겼을 때 최소 비용을 구해야 하는 점이다.
어려웠던 문제였다. dp는 해도해도 어렵다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, M, res = 987654321;
int A[101];
int C[101];
int dp[101][10001];

void solution() {
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 10001; j++) {
            if (j - C[i] >= 0) {
                dp[i][j] = max(dp[i-1][j], A[i] + dp[i - 1][j - C[i]]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }

            if (dp[i][j] >= M) {
                res = min(res, j);
            }
        }
    }

    cout << res;
}

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

    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }

    solution();

    return 0;
}