BOJ - 앱(7579)

골드3 : 동적 계획법 문제이다.

생각

이 문제는, BOJ - 평범한 배낭(12865)과 매우 비슷하다. 한번 푸는 것이 좋다.

이 문제는 memory의 범위가 매우 크기 때문에, 이 것을 기준으로 로직을 짜면 메모리가 터진다. 그래서 반대로 cost를 어떤 기준으로 만들 수 있는 지를 고민하여 코드를 짰다.

정의

dp[i][j] = i번째 앱까지 비활성화했을 때 j의 비용까지 만들 수 있을 때 메모리의 최댓값

메모리의 최댓값이라 잡은 이유는, 최소 Cost로 최대 메모리를 지우는 것이 합리적이기 때문이다.

5 60
30 10 20 35 40
3 0 3 5 4

현재 비용 : 3 현재 메모리 : 30
  0   0   0  30  30  30  30  30  30  30  30  30  30  30  30  30

현재 비용 : 0 현재 메모리 : 10
 10  10  10  40  40  40  40  40  40  40  40  40  40  40  40  40

현재 비용 : 3 현재 메모리 : 20
 10  10  10  40  40  40  60  60  60  60  60  60  60  60  60  60

현재 비용 : 5 현재 메모리 : 35
 10  10  10  40  40  45  60  60  75  75  75  95  95  95  95  95

현재 비용 : 4 현재 메모리 : 40
 10  10  10  40  50  50  60  80  80  85 100 100 115 115 115 135

6

새로운 앱이 추가됨에 따라, 그 Cost에서 가질 수 있는 메모리의 최댓값을 가지고 있으면 문제는 해결된다.

점화식

dp[j] = max(temp[j], temp[j-nowCost] + nowMem)

temp는 i-1개의 앱을 사용했을 때의 정보를 갖고 있는 dp이다. 이전 평범한 배낭 문제에서도 이전 depth의 정보만을 가져다가 사용하기 때문에 메모리가 낭비된다.

이 문제는, 새로운 앱이 추가되었을 때, 현재 Cost에서 최대 메모리를 지우는 것을 목표로 코드를 짜면 된다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
#define COSTMAX 10000
#define APPMAX 100
using namespace std;
typedef long long ll;
int costLimit = 0;
int N, M;
ll dp[COSTMAX+1];
ll temp[COSTMAX+1];
int mem[APPMAX+1];
int cost[APPMAX+1];
ll ans;
 
void print(int i){
    cout << "현재 비용 : " << cost[i] << " 현재 메모리 : " << mem[i] << '\n';
    for (int i = 0; i <= costLimit; i++) {
        cout << setw(3) << dp[i] << " ";
    }cout << '\n' << '\n';
}
 
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> mem[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> cost[i];
        costLimit += cost[i];
    }
 
    for (int i = 1; i <= N; i++) {
        memcpy(temp, dp, sizeof(dp));
        int nowCost = cost[i];
        int nowMem = mem[i];
 
        for (int j = nowCost; j <= costLimit; j++) {
            dp[j] = max(temp[j], temp[j-nowCost] + nowMem);
        }
        print(i);
    }
    for (int i = 0; i <= costLimit; i++) {
        if (dp[i] >= M) {
            ans = i;
            break;
        }
    }
    cout << ans << '\n';
 
    return 0;
}

Reference

• 백준(7579번) - 평범한 배낭