BOJ 7579 앱

개요

BOJ 7579 앱

• 백준 온라인 저지 7579번 문제
• BOJ 29단계

C++

#include <iostream>
using namespace std;

int N, M, sum;
int m[101];
int c[101];
int D[101][10001];

int solve() {
    for(int i=1; i<=N; i++){
        for(int x=0; x<=sum; x++){
            if(c[i] > x) {
                D[i][x] = D[i-1][x];
            } else {
                D[i][x] = max(D[i-1][x], D[i-1][x-c[i]]+m[i]);
            }
        }
    }
    for (int i=0; i<=sum; i++) {
		if (D[N][i] >= M) {
		    return i;
		}	
	}
	return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> m[i];
    }
    for(int i=1; i<=N; i++) {
        cin >> c[i];
        sum += c[i];
    }
    cout << solve();
}