백준 7579.cpp [앱]

이 문제를 풀면서 어려웠던 건.. 이 문제가 DP가 맞는가? 였다. 요즘 (DP, 그리디, 브루트포스) 종류의 문제를 만나면 갈피를 잡지 못하는 것이 가장 힘들다. 배낭 문제라는 사실을 알았을 땐, 아.. 그치 배낭 문제지..라고 금방 이해되지만 혼자서 그 생각을 해내는 게 가장 어려운 것 같다.

 

---

 

 이 문제는 최근에 만난 DP 문제들처럼 약간의 응용이 필요하다. 문제의 목표는 M이상의 메모리를 확보하면서 가장 적은 Cost를 사용하는 것이 목표이다. 그렇다면 DP 관계(?)를 설정할 때 다음과 생각해 볼 수 있다.

 

• DP 배열은 2차원 배열로 구성하고 배낭 문제 처럼 접근한다고 하자.
• 그렇다면 1, 2 선택지 중에 어떤 것을 골라야할까?
• DP[앱의 index][앱의 memory] 로 구성
• DP[앱의 index][앱의 복구 cost] 로 구성

기존의 배낭 문제처럼 접근하면 아마 첫 번째 구성을 선택할지도 모른다. 그럼 int DP[101][10,000,000] 의 배열이 필요하고 약 4GB의 메모리가 필요하기 때문에 메모리 초과가 발생해 문제를 풀 수 없다.

 

즉, 두 번째 구성을 사용해야 한다. 이 문제에서 구하고자 하는 건 최소 Cost 이기 때문에 자연스러운 사고 흐름이 아니지만 DP 문제에서 이런 식으로 구하고자 하는 것을 먼저 구하고 조건에 맞는 답을 선택하는 방식의 문제들이 꽤 있다. (골드 구간에 꽤 있음)

 

코드는 배낭 문제 알고리즘과 거의 동일하므로 코드 설명은 건너뛰겠다. 이 문제는 어떻게 메모리 초과를 회피할 것인지, 배낭 문제임을 떠올릴 수 있는지가 가장 중요한 포인트 같다.

 

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define F first
#define S second
#define pii pair<int, int>
#define MAXC 10001
#define INF (int)1e9

int dp[101][MAXC];

int main() {
    int N, M;
    cin >> N >> M;

    vector<pii> apps(N + 1);
    
    for(int i = 1; i <= N; i++) cin >> apps[i].F;
    for(int i = 1; i <= N; i++) cin >> apps[i].S;

    // fill_n(dp, MAXC, 0);
    memset(dp[0], 0, sizeof(dp));

    int n_mem, 
        n_cost,
        ans = INF;

    for(int i = 1; i <= N; i++) {
        n_mem = apps[i].F,
        n_cost = apps[i].S;

        for(int j = 0; j < 10001; j++) { 
            if(n_cost <= j)
                dp[i][j] = max(dp[i - 1][j], n_mem + dp[i - 1][j - n_cost]);           
            else
                dp[i][j] = dp[i - 1][j];

            if(dp[i][j] >= M) {
                ans = min(ans, j);
            }
        }
    }
    cout << ans;
}