문제

문제 분석

bruteforce로 완전탐색하면 풀린다. 다만 시간 복잡도가 문제이다.

M(목표 메모리)을 60 확보해야할 때, 아래와 같이 반복되는 조사 대상이 생긴다.
60->50->30->(다음)
60->40->30->(다음)
따라서, DP를 사용할 수 있을 것 같다.

문제는 M이 10^7이라 table의 space complexity가 문제가 된다.

대신 용량이 cost c이고, app a0..i 까지 고려할 때의 최대를 dp 에 저장하는 것을 생각해보자.
dp[c][ai] 는 ai를 포함하거나, 포함하지 않는 경우 중 하나가 최적일 것이다.
dp[c][ai] = max( dp[c-{ai의cost}][ai-1]+{ai의 메모리}, dp[c][ai-1]) 로 결정된다는 소리이다.

알고리즘

• dp(knapsack)

자료구조

• 2d vector: N * C^2

결과

• 성공

/*
app1~N 까지 넣을까 말까로 분할 정복
DP가능-> BUT 메모리를 축으로 하기엔 메모리 초과 가능
맵+메모이제이션으로 필요한 것만 저장하려고 했으나 역시 메모리 초과.
대신, cost를 축으로 knapsack으로 가능.
*/
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 100;
const int MAX_COST = 10000;
const int MAX_INT = ~(1<<31);

int N, M; // N: num of app, M: mem of goal

vector<int> memVec(MAX_N);
vector<int> costVec(MAX_N);
// r: cost, c: app, val: max Mem
vector<vector<int>> table( MAX_COST+1, vector<int>(MAX_N, 0)); 

int main ( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> M;
    for ( int i = 0; i < N; i++ )
        cin >> memVec[i];
    for ( int i = 0; i < N; i++ )
        cin >> costVec[i];

    for ( int costIdx = 0; costIdx <= MAX_COST; costIdx++ ){
        if ( costVec[0] <= costIdx ){
            table[costIdx][0] = memVec[0];
        }
    }
    for ( int appIdx = 1; appIdx < N; appIdx++ ){
        for ( int costIdx = 0; costIdx <= MAX_COST; costIdx++ ){
            int remainCost = costIdx - costVec[appIdx];
            int newMem;
            if ( remainCost < 0 )
                newMem = 0;
            else {
                newMem = table[remainCost][appIdx-1] + memVec[appIdx];
            }

            if ( table[costIdx][appIdx-1] < newMem )
                table[costIdx][appIdx] = newMem;
            else 
                table[costIdx][appIdx] = table[costIdx][appIdx-1];
        }
    }

    int lastAppIdx = N -1;
    for ( int costIdx = 0; costIdx <= MAX_COST; costIdx++ ){
        if( table[costIdx][lastAppIdx] >= M ){
            cout << costIdx;
            break;
        }
    }
}

Other

DP 가 가능할 때, 처음 생각한 축이 안된다고 당황하지 말자.
축을 줄이든, 늘리든, 다른 축을 생각하든 해보자.