[BOJ 7579] 앱

이 문제는 메모리 초과로 인해서 매개변수를 수정해서 DP를 선언해야 한다.

 

 

 

최소 비용을 찾기 위해서 DP를 인덱스 하나와 바이트를 이용하면, 메모리 초과가 발생한다.

 

 

 

따라서, 인덱스 하나와 비용을 이용해서 최대의 바이트를 가지도록 관계식을 세워야 한다.

 

 

 

DP[i][j]일 때,

 

 

 

i = 비활성화할 메모리 인덱스의 시작

j = 쓸 수 있는 비용

 

 

 

 

해설코드(C++).

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N, M;
int c[101];
int m[101];
long long dp[101][10001];
 
long long func(int cur, int cost){
    if(dp[cur][cost] != -1)
        return dp[cur][cost];
        
    if(cur == N)
        return 0;
        
    dp[cur][cost] = func(cur + 1, cost);
    if(cost - c[cur + 1] >= 0)
        dp[cur][cost] = max(dp[cur][cost], m[cur + 1] + func(cur + 1, cost - c[cur + 1]));
        
    return dp[cur][cost];
}
 
int main() {
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        cin >> m[i];
        
    for(int i = 1; i <= N; i++)
        cin >> c[i];
        
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i <= 10000; i++){
        long long result = func(0, i);
        if(result >= M){
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}