(c++) 동적계획법 7579번: 앱

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

7579번: 앱

 

 

 

문제 개요

 

 

배낭 문제는 메모이제이션을 [물품의 용량] [물품의 개수] = 물건의 가치

위와 같이 사용했지만, 이 문제를 보면 주어지는 M의 용량은 10,000,000 이다.

 

배낭 문제와 비슷한 방법으로 푼다면

cache[10,000,000][100] 이라는 말도 안되는 배열을 사용하게 된다.

 

그래서 반대로

비교적 최대 값이 10,000인 비활성화 결과를 메모이제이션으로 사용할 것이다.

cache[비활성화 비용의 합] = 메모리

 

sum = 비활성화 비용 전체 합

배열 c = 비활성화 비용

배열 memory = 앱 사용 메모리

for (int i = 0; i < n; i++) {
    for (int j = sum; j >= c[i]; j--) {
        cache[j] = max(cache[j], cache[j - c[i]] + memory[i]);
    }
}

 

 

메모리가 최대인 경우를 구하는 이유는

cache[j]의 j 값이 우리가 찾고자 하는 비활성화 비용의 합이다.

 

for (int i = 0; i <= sum; i++) {
    if (cache[i] >= m) {
        cout << i;
        break;
    }
}

 

비활성화 비용이 작으면서 메모리의 크기가 M의 비용과 같거나 크다면

정답인 최소 비활성화 비용을 구할 수 있게 된다.

 

 

 

 

 

코드

 

 

 

 

#include <bits/stdc++.h>

using namespace std;
int n, m, sum;
int memory[100], c[100];
int cache[10000];

void cost() {
    for (int i = 0; i < n; i++) {
        for (int j = sum; j >= c[i]; j--) {
            cache[j] = max(cache[j], cache[j - c[i]] + memory[i]);
        }
    }
}

int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> memory[i];
    }
    
    for (int j = 0; j < n; j++) {
        cin >> c[j];
        sum += c[j];
    }
    cost();
    for (int i = 0; i <= sum; i++) {
        if (cache[i] >= m) {
            cout << i;
            break;
        }
    }
}