[백준/C,C++] 7579번: 앱

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

7579번: 앱

풀이

해당 문제에서 앱의 개수는 100개 이하이고, 확보해야하는 메모리는 10,000,000바이트 이하입니다.

 

100 x 10,000,000 는 10억으로 너무 크기 때문에,

 

비활성화 했을 경우의 최대 비용인 100을 사용해 DP 점화식을 짜야합니다.

 

DP[i]를 i의 비용이 주어졌을때 확보할 수 있는 최대 메모리라고 가정해봅시다.

 

5 60

30 10 20 35 40

3 0 3 5 4

 

의 예제로 보겠습니다.

 

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
30	0	0	0	30	30	30	30	30	30	30	30	30	30	30	30	30
10	10	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
20	10	10	10	40	40	40	60	60	60	60	60	60	60	60	60	60
35	10	10	10	40	40	45	60	60	75	75	75	95	95	95	95	95
40	10	10	10	40	50	50	60	80	80	85	100	100	115	115	115	135

 

메모리가 20, 비활성화 비용이 3인 세번째 어플리케이션을 보겠습니다.

 

6의 비용이 주어졌을때 DP[i] = max(DP[i], DP[i - cost] + memory)로 점화식을 나타낼 수 있는데,

 

현재 어플리케이션을 비활성화 한 것과 하지 않은 것 둘 중 메모리가 큰 쪽을 선택한다고 볼 수 있습니다.

 

DP[6]은 기존에 40이었고, 20을 활성화 하기 위해선 3의 비용이 필요하기에

 

DP[3]인 40에 20을 더해보면 60의 메모리를 확보할 수 있습니다.

 

#include <iostream>

using namespace std;

const int MAX = 100;

int N, M, total;
int memory[MAX + 1], cost[MAX + 1];
int cache[MAX * MAX + 1];

int main(void)
{
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> memory[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> cost[i];
        total += cost[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = total; j >= cost[i]; j--) {
            cache[j] = max(cache[j], cache[j - cost[i]] + memory[i]);
        }
    }

    for (int i = 0; i <= total; i++) {
        if (cache[i] >= M) {
            cout << i;
            return 0;
        }
    }

    return 0;
}

반례

Input

10 3000
157 912 345 599 166 454 991 277 351 458
10 9 8 34 2 55 70 31 58 24

Output

123