[Algorithm] 7579: 앱

📦7579: 앱

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-18
문제 확인하기

풀이

• DP를 많이 풀어보지 않아서 그런가 아직도 DP 개념이 좀 어렵다.
• dp[i][j] 는 i 번째 앱이 j 비용을 사용해서 확보할 수 있는 최대 메모리를 뜻한다.
• dp[i-1][j-cost[i]]+bytes[i] 을 통해 이전 앱에서 j-cost[i] 비용으로 확보할 수 있는 메모리 + 현재 앱에서 확보할 수 있는 메모리를 갱신해준다.

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
 
int bytes[101], cost[101];
int dp[101][10001];
int N, M, sum = 0, res = INT32_MAX;
 
void Input(){
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> bytes[i];
    }
    for(int i=1; i<=N; i++) {
        cin >> cost[i];
        sum += cost[i];
    }
 
}
 
void Solution(){
    for(int i=1; i<=N; i++){
        for(int j=0; j<=sum; j++){
            if(j >= cost[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]]+bytes[i]);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            if(dp[i][j] >= M) {
                res = min(res, j);
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
    cout << res << endl;
 
    return 0;
}