[알고리즘] 백준 7579 - 앱

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

int N, M, sum;
int Arr[101], Cos[101];
int DP[101][10001];

int main(){
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        cin >> Arr[i];
    }
    for(int i=1; i<=N; i++){
        cin >> Cos[i];
        sum += Cos[i];
    }
    
    for(int i=1; i<=N; i++){
        for(int j=0; j<=sum; j++){
            if(j - Cos[i] >= 0){
                DP[i][j] = max(DP[i][j], DP[i-1][j - Cos[i]] + Arr[i]);
            }
            DP[i][j] = max(DP[i][j], DP[i-1][j]);
        }
    }
    
    for(int i=0; i<=sum; i++){
        if(DP[N][i] >= M){
            cout << i << "\n";
            break;
        }
    }

    return 0;
}