이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 106 번째 글 입니다.
목차
골드3 : 동적 계획법 문제이다.
생각
이 문제는, 백준(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;
}