백준 No.7579 [앱]

BOJ No.7579 [앱]

---

 Problem 

7579번: 앱

---

 Code 

#include <iostream>
#include <vector>
#define memory first
#define cost second
 
using namespace std;
typedef pair<int, int> PII;
 
int cost_max = 0;
int N, M;
vector<PII> apps;
vector<int> dp;
// dp[c] : c 원이 드는 경우에 제거 가능한 최대 용량
 
int solve() {
    dp[apps[0].cost] = apps[0].memory;
 
    for (int i = 1; i < N; i++) {
        for (int c = cost_max; c >= apps[i].cost; c--)
            if (dp[c - apps[i].cost] != -1)
                dp[c] = max(dp[c], dp[c - apps[i].cost] + apps[i].memory);
 
        if (dp[apps[i].cost] < apps[i].memory) dp[apps[i].cost] = apps[i].memory;
    }
 
    for (int c = 0; c <= cost_max; c++)
        if (dp[c] >= M) return c;
 
    return 0;
}
 
int main() {
    cin >> N >> M;
    apps.resize(N, PII(0,0));
 
    for (auto& e : apps) cin >> e.memory;
    for (auto& e : apps) {
        cin >> e.cost;
        cost_max += e.cost;
    }
    dp.resize(cost_max + 1, -1);
 
    cout << solve();
}

---

 How to sovle 

  백준 No.12865 [평범한 배낭]에서 약간의 발상의 전환을 요구하는 문제였던 것 같다. 배낭 문제는 일정 무게 이하만 챙길 수 있으며, 이때의 최대 가치를 취하는 문제였고, 이 문제는 반대로 일정 메모리를 넘으면서 최소 비용을 취하는 문제였다.

 

  이 문제의 메모리는 배낭 문제의 무게에 상응하고, 이 문제의 비용은 배낭 문제의 가치에 상응하는 것 이므로 2차원 dp의 x축을 메모리로 잡고 풀려고 했지만, 메모리의 최대값이 천만이므로, 메모리 초과가 발생할 수 있다. 따라서 이 문제는 x축을 비용으로 잡고 풀어야 했다.

  위 문제는 아래 입력에 대한 예시이다.

  apps[0] 만 고려할 땐, apps[0].cost 에 해당하는 dp값만 apps[0].memory로 바꾸어 주면 되므로 굳이 반복문을 써서 할 필요가 없어서 #16 line에서 따로 정의를 해 주었다.

 

  cost_max 의 값은 #37 ~ #40 line 에서 apps[ i ].cost 값을 입력을 받을 때 모든 비용들을 다 합한 비용이다. cost_max 의 가능한 최대 값은 100 * 100 인 10,000 이어서 애초에 const int cost_max = 10000; 로 해도 무방하다.

 

  그렇게 i 가 1 에서 N - 1 까지 돌면서 내부의 2번째 for문은 c 가 cost_max 부터 현재 앱의 비용까지 또 돈다. 위의 사진에 파란 부분이 값의 갱신이 이루어지는 부분들이다. 이때 c 가 좌측에서 우측이 아닌, 우측에서 좌측 (cost_max 에서 apps[ i ].cost 까지) 간 이유는 해당 apps[ i ]의 중복 사용을 막기 위해서 이다. 처음에는 좌에서 우로 가는 코드를 짰었는데, 이때 

에서 문제가 발생하였다. 만약 좌에서 우로 검사한다면, 

이와 같이 계속해서 현재 app의 cost의 배수 index에서 app의 중복사용으로 값이 갱신이 되기 때문에 문제가 된다.

 

  #20 ~ #21 line 의 의미는, 현재 c의 값에서 현재 app의 비용을 뺀 곳의 dp값이 존재한다면 (-1이 아니라면) 그 값의 dp값인 dp[c - apps[ i ].cost] 에 apps[ i ].memory 값을 얹은 값을 dp[ c ]에 저장해라. 단, 현재 dp[ c ]의 값보다 더 큰 값이 나왔을 때! 로 정리할 수 있다.

 

  #23 line 은 현재 index에 해당하는 app 하나를 지웠을 때 발생하는 비용에 대한 dp값을 갱신해 주는 것이다. 

 

  dp값의 갱신이 전부 끝난 후 dp[C]의 의미는, C의 비용으로 가장 많이 확보할 수 있는 메모리의 크기가 되므로 #26 ~ #27 line 과 같이 비용을 늘려가면서 가장 먼저 M의 메모리 이상의 값이 나왔을 때 return 하면 된다. 이는 lower_bound 를 이용해서도 구할 수 있을 것이다.