7579 앱

N개의 앱이 작동중일 때 M만큼의 메모리를 확보하려 할 때 앱 비활성화 비용의 최소값을 구하는 문제다.

dp를 d[N][M]로 잡으면 10억이므로 메모리 초과가 난다. 그렇기 때문에 d[N][s] 로 생각 한다.

앱 비활성화 비용의 합이 s일 때 확보할 수 있는 최대 메모리값을 저장하는 것이다.

<코드>

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int a[101], b[101], n, m, d[10001], sum, i, j;
 
int main() {
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    for (i = 0; i < n; i++) scanf("%d", &b[i]), sum += b[i];
    for (i = 0; i < n; i++) for (j = sum; j >= b[i]; j--) {
        d[j] = max(d[j], d[j - b[i]] + a[i]);
    }
    for (i = 0; i < sum && d[i] < m; i++);
    printf("%d\n", i);
    return 0;
}