BOJ 7579 - 앱

www.acmicpc.net/problem/7579

7579번: 앱

 

냅색 응용 문제이다.

dp 1차원 배열을 dp[j] : 비용이 j일때 확보가능한 메모리로 정의하고 

점화식을 dp[j] = max(dp[j], dp[j - cost[i]] + memory[i]) 로 정의할 수 있다.

-> 비용이 j 일때 확보가능한 메모리는, i 번째 앱을 활성화하지 않았을때의 메모리와 i번째 앱을 활성화 했을때의 메모리 값 중 최대치로 정의한다.

여기서 정의한 dp 배열은 메모리에 대한 부분만 담겨 있기 때문에, 문제에서 요구하는 최소비용과 직접적으로 연결된것은 아니므로 최소비용을 구하기 위한 별도의 로직을 작성해야한다.

이를 위해 반복문을 하나 만들어서 최소 M 메모리 이상 확보할 수 있게하는 최소한의 비용값을 구해준다.

 

 

- C++

#include <iostream>
 
using namespace std;
 
int N, M; // 활성화된 앱 갯수, 확보해야할 메모리 
pair<int, int> app[101]; // 점유 중인 메모리 바이트 m, 비활성 비용 c 
int dp[10001]; // 비용이 i 일때, 확보 가능한 메모리 
int sum; 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> M; 
    for (int i = 1; i <= N; ++i) cin >> app[i].first;
    for (int i = 1; i <= N; ++i) {
        cin >> app[i].second;
        sum += app[i].second;    
    }
    
    for (int i = 1; i <= N; ++i) 
        for (int j = sum; j >= app[i].second; --j) 
            dp[j] = max(dp[j], dp[j - app[i].second] + app[i].first);
            
    int answer = 0;
    while(1) {
        if (answer < sum && dp[answer] < M) answer++;
        else break;
    }
    cout << answer;
    
    return 0;
}