[BOJ] 백준 7579 앱

문제 링크

www.acmicpc.net/problem/7579

7579번: 앱

 

풀이

각 앱별로 사용 중인 메모리 $m$, 비활성화 했을 경우 비용 $c$가 주어집니다.

일반적으로 생각했을 땐 메모리의 모든 범위에 대해 최소 비용을 구하는 배낭 dp인데, 메모리의 범위가 너무 커 배열로 잡을 수 없습니다.

 

관점을 좀 달리하여 모든 비용에 대해 확보할 수 있는 최대의 메모리를 구해줍시다. 비용의 범위는 최대 100이므로 충분히 가능합니다.

그 후 비용 0부터 올라가며 우리가 필요한 메모리 $M$바이트를 확보할 수 있는지 체크해주면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;
using ll = long long;


int n, m;
int p[111], d[11'111];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i < n + 1; i++) {
        cin >> p[i];
    }
    for (int i = 1; i < n + 1; i++) {
        int c;
        cin >> c;
        for (int j = 10'000; j >= c; j--) {
            d[j] = max(d[j], d[j - c] + p[i]);
        }
    }

    for (int i = 0; i <= 10'000; i++) {
        if (d[i] >= m) {
            cout << i;
            break;
        }
    }
}