앱

마지막 문제답게 발상 자체 난이도도 있고 문제를 주의깊게 읽지 않으면 틀리는 함정까지 마련되어 있다. 풀이를 읽기 전에 문제를 한번 꼼꼼하게 다시 읽어보는 것을 추천한다.

우선 문제를 봤을 때 물건을 종류 별로 하나씩만 선택할 수 있는 점, 무게와 비용의 개념이 있는 점 등을 미루어보아 0/1 Knapsack 문제는 맞는 것 같은데, 특정한 무게를 정확하게 채워야하는 것이 아니라 초과해도 상관이 없다는 특이한 조건이 추가되어 있다. 또한, 가치를 최대로 하는 것이 아니라 반대로 물건을 선택할 때 비용이 있어 그 비용을 최소화 하는 것이 목적이다.

※ 앱의 재시작 시간 → 비용, 앱의 메모리 사용량 → 무게, 확보해야하는 메모리 최소량 → 배낭 용량으로 치환해 작성하였습니다.

풀이 1

발상 1

비둘기집 원리에 의해 최적 사례에서 물건 무게의 총합이 배낭의 용량을 초과하는 경우, 모든 각 물건의 무게는 그 초과한 양보다 커야한다. 만약 초과한 무게보다 작은 무게의 물건이 있다면 그 물건을 선택하지 않아도 무게 조건을 충족할 수 있으므로 최적이 아니게 된다.
최종 무게가 배낭의 용량을 초과하더라도 비용을 최소로 줄이는 것이 목적이므로 현재 배낭 용량을 초과하는 물건도 비용이 더 적다면 집어넣을 수 있다. 위의 두 가지 사실을 조합해보면 다음과 같은 발상이 가능하다. “현재 배낭 용량이 현재 물건 무게보다 작더라도 무시하고 추가해 비용을 갱신하자.” 가장 처음 넣는 물건의 무게를 줄여서라도 최적값을 얻어내고 이후 현재 물건 무게 보다 큰 용량에 대해서는 기존 배낭 문제 풀이와 동일하게 진행한다. 초과하는 용량보다 작은 무게를 가진 물건 선택도 별도로 체크할 필요가 없는게 어차피 초과하는 용량보다 작은 무게의 물건을 포함하는 선택지는 1번 항목의 논리에 따라 최적값 후보에서 반드시 탈락될 수 밖에 없기 때문이다.

점화식 1

⎩ ⎨ ⎧ n_{i, j} = 1 \sim i 번째 앱 중에서 재시작했을 때 j 만큼의 용량을 삭제하는 최소 비용 v_{i} = i 번째 앱 재시작 시간 (비용) w_{i} = i 번째 앱 메모리 소비량 (무게)

n_{i, j} = ⎩ ⎨ ⎧ min (n_{i - 1, j}, v_{i}) min (n_{i - 1, j}, n_{i - 1, j - w_{i}} + v_{i}) if j < w_{i} else

코드 1

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct app {
    int w, v;
};
int main() {    
    int n, m; cin >> n >> m; vector<app> arr(n + 1); 
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].w;
    }
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].v;
    }
    // 비용이 0인 앱들은 탐색하기 전에 미리 제거해놓기
    for (int i = n; i >= 1; i--) {
        if (arr[i].v == 0) {
            m -= arr[i].w;
            arr.erase(arr.begin() + i);
            n--;
        }
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 21e8));
    dp[0][0] = 0; // 기저 사례 : 앱을 하나도 재시작 하지 않은 경우
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        for (int j = 1; j <= m; j++) {
            int rm = j - arr[i].w < 0 ? 0 : j - arr[i].w;
            int s1 = dp[i - 1][j];
            int s2 = dp[i - 1][rm] + arr[i].v;
            dp[i][j] = s1 < s2 ? s1 : s2;
        }
    }
    cout << dp[n][m];
    return 0;
}

풀이 2

풀이1은 상당히 만족스러운 풀이였다. 여길보고 저길봐도 논리적으로 완벽한 풀이다. 오늘도 문제 하나를 해결했다는 뿌듯한 마음가짐으로 코드를 제출한다. 그런데 이게 뭐지? 맞았습니다!가 쓰여있어야 할 공간에 메모리 초과라는 글자가 쓰여있다. 당황한 당신은 다시 문제를 천천히 읽어보기 시작한다. 아무리 봐도 틀릴 구석이 없다. 점점 채점 프로그램과 데이터가 의심스럽기 시작한다. 그런데 생각해보니 채점 결과가 ‘틀렸습니다.‘가 아닌 ‘메모리 초과’였다. 메모리가 어쨌다는건가 싶어 입력 크기 제한을 다시 한번 찬찬히 살펴보기 시작한다. 아뿔싸,,! 배낭 용량의 최대치가 무려 $1 0^{7}$ 이다. 우리의 dp 배열의 크기는 $1 0^{7} \times 1 0^{2}$ , 10억개짜리 배열이 된다. int는 4바이트니까 우리는 지금 40억 바이트짜리 배열을 잡은 것이다. 단위를 환산하면 4GB다. 이 문제의 메모리 사용 제한은 128MB다. 제한량의 무려 40배 가까운 메모리를 사용한 것이다.

이처럼 풀이 자체의 논리가 완벽해보여도 입력의 크기 또한 주의깊게 살펴야한다.

이렇게 풀이1이 완전히 무산됐다. 풀이 발상 자체는 훌륭했지만 파멸적인 메모리 요구량을 감당하지 못했다. 지금까지의 모든 배낭 문제들은 모두 물건 수 x 배낭 최대 용량의 크기를 가진 2차원 배열로 해결해왔는데 최대 용량이 $1 0^{7}$ 이라니.. 다른 알고리즘을 찾아야만 하는걸까? 그렇지 않다.

발상 2

입력 크기를 보면 물건을 선택하는 비용의 최댓값은 100으로 비교적 매우 작다. 물건 $100$ 개의 비용이 모두 $100$ 이어도 비용의 총합은 $10000$ 을 넘지 않는다. 즉,

{n_{i, j} = 1 \sim i 번째 앱 중에서 재시작했을 때 j 만큼의 용량을 삭제하는 최소 비용

은 $j$ 의 최댓값이 $1 0^{7}$ 이기 때문에 배열 생성이 불가능해도

{n_{i, j} = 1 \sim i 번째 앱 중에서 재시작했을 때 j 만큼의 비용으로 삭제할 수 있는 최대 용량

은 $j$ 의 최댓값이 $10000$ 이기 때문에 가능하다는 것이다. 이제 문제가 정말 간단해졌다. 각 비용으로 삭제할 수 있는 최대 용량이 삭제해야 하는 목표 용량보다 같거나 클 때 마다 비용을 최소 갱신하면 최소 비용을 구할 수 있다.

점화식2

⎩ ⎨ ⎧ n_{i, j} = 1 \sim i 번째 앱 중에서 재시작했을 때 j 만큼의 비용으로 삭제할 수 있는 최대 용량 v_{i} = i 번째 앱 재시작 시간 (비용) w_{i} = i 번째 앱 메모리 소비량 (무게) M = 삭제해야하는 최소 메모리 용량

n_{i, j} = ⎩ ⎨ ⎧ max (n_{i - 1, j}, w_{i}) max (n_{i - 1, j}, n_{i - 1, j - v_{i}} + w_{i}) if j < v_{i} else

답은 $n_{i, j} \geq M$ 을 만족하는 $j$ 중 최솟값이다.

코드2

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct app {
    int w, v;
};
int main() {    
    int n, m; cin >> n >> m; vector<app> arr(n + 1); int k = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].w;
    }
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].v;
        k += arr[i].v;
    }
    for (int i = n; i >= 1; i--) {
        if (arr[i].v == 0) {
            m -= arr[i].w;
            k -= arr[i].v;
            arr.erase(arr.begin() + i);
            n--;
        }
    }    
    if (k == 0) {
        cout << 0;
        return 0;
    }
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    int mn = 21e8;    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < arr[i].v; j++) {
            dp[i][j] = dp[i - 1][j];            
        }
        for (int j = arr[i].v; j <= k; j++) {
            int s1 = dp[i - 1][j - arr[i].v] + arr[i].w;
            int s2 = dp[i - 1][j];
            dp[i][j] = max({ dp[i][j], s1, s2 });
            if(dp[i][j] >= m) { // 계산된 메모리 용량이 목표치를 달성한 경우
                mn = mn < j ? mn : j; // 최소 비용 갱신
            }
        }
    }
    cout << mn;
    return 0;
}

정말 고수라면 입력 크기를 보고 처음부터 풀이2를 떠올릴 수도 있지만, 틀렸을 때 원인을 분석하고 풀이1이 틀린 이유를 찾는 능력도 매우 중요하다.

🪴 Quartz 4.0

Explorer

앱