[DP] 백준 7579 앱 C++

 

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

7579번: 앱

 

#include<iostream>
#include<vector>
#define INF 1234567891
using namespace std;

int n, m, a, ans=INF, sum;
int dp[101][10001];
vector<int> M;
vector<int> C;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;

    C.push_back(0);
    for (int i = 0; i < n; i++) {
        cin >> a;
        M.push_back(a);
    }

    M.push_back(0);
    for (int i = 0; i < n; i++) {
        cin >> a;
        C.push_back(a);
        sum += a;
    }

    for (int j = 0; j < sum + 1; j++) {
        for (int i = 1; i < n + 1; i++) {
            if (j >= C[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - C[i]] + M[i - 1]);
            else dp[i][j] = dp[i - 1][j];
            
            if (dp[i][j] >= m) {
                ans = min(ans, j);
                break;
            }
        }
    }

    cout << ans;
}