[백준] 7579: 앱(feat. DP)

앞선 코테에서 생각 이상으로 다이나믹 프로그래밍이 까다롭고 출제도 자주 된다는 것을 알게 되어 다이나믹 프로그래밍 문제를 열심히 준비하고 있다.

그런데 이전에 풀었던 풀이마저도 가물가물해서 복습도 병행하고 있다.

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

7579번: 앱

여기서는 어떻게 비용과 확보할 수 있는 메모리를 어떻게 연관짓느냐가 쟁점이다.

이럴 때는 인덱스로 메모이제이션되는 값에 접근하는데, 인덱스를 어떤 걸로 삼아야하는지를 결정하면 된다.

이전의 비용으로 확보할 수 있는 메모리의 양에 추가적으로 비용을 들여서 추가적으로 확보되는 메모리를 파악할 수 있으므로 dp 배열의 인덱스는 비용, 특정 인덱스마다는 확보할 수 있는 메모리를 저장하면 된다.

 

$dp[i] = $ 비용 $i$로 최대한 세이브할 수 있는 메모리

 

그 다음으로 중요한 일은 dp 배열을 뒤에서부터 접근해야한다.

주어진 앱을 순회하면서 각 앱마다 이전 앱까지를 고려해 각 비용마다의 최대한 확보할 수 있는 메모리를 갱신한다.

예를 들어 i를 전체 비용으로, j를 현재 확인하고 있는 앱의 인덱스라고 한다면 점화식은 아래와 같다.

 

$dp[i] = max(dp[i], dp[i - cost[j]] + memory[j]$

$cost[j] = $j 앱을 비활성화하는 데 드는 비용

$memory[j] = $ 앱을 비활성화할 시 확보할 수 있는 메모리

 

/**
 * dp[i] = i 비용으로 확보할 수 있는 최대 메모리
 * 약간 변형된 knapsack 문제
 **/
#include <iostream>
#include <bits/stdc++.h>
#define MAX 100
int memory[MAX + 1];
int cost[MAX + 1];
int dp[MAX * MAX + 1];
using namespace std;

int main(void){
    int n,m;
    int sum = 0;
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        cin >> memory[i];
    }
        for(int i = 0;i < n;i++){
        cin >> cost[i];
        sum += cost[i];
    }

    for(int i = 0;i < n;i++){
        int c = cost[i];
        for(int j = sum;j > 0;j--){
            if(j >= c){
                dp[j] = max(dp[j], dp[j - c] + memory[i]);
            }
        }
    }
    int answer = -1;
    for(int i = sum;i > 0;i--){
        if(dp[i] >= m){
            answer = i;
        }
    }
    cout << answer;
}