백준 7579 - 앱(C++)

문제 링크입니다. https://www.acmicpc.net/problem/7579

7579번: 앱

배낭 문제를 이용한 DP 문제입니다.

원하는 메모리를 얻기 위해 지워야할 메모리를 최소비용으로 구하는 문제입니다.

 

저는 dp[x][y]  = k 를 이용했습니다.

의미는 X개의 앱까지 확인했을 때, Y 비용으로 얻을 수 있는 최대의 메모리입니다.

 

문제의 예제 입력으로 확인해보겠습니다.

 

배열의 값이 다음과 같이 나옵니다.

첫번째 줄을 보면, 1번 앱만을 확인했을 때, 얻을 수 있는 최대의 메모리입니다.

1번 앱의 비용은 3이니, 3부터는 계속 30의 값으로 고정된 것을 볼 수 있습니다.

 

두번째 줄을 보면, 0의 비용으로 10의 메모리를 얻을 수 있습니다.

따라서 값이 10씩 더해지는 것을 확인할 수 있습니다.

 

세번째 줄을 보면, 3번째 앱은 3의 비용으로 20의 메모리를 억을 수 있습니다.

따라서 6의 비용부터 얻을 수 있는 메모리가 60이 된 것을 볼 수 있습니다.

 

이와 같은 방법으로 값을 찾아나갑니다.

 

 for(int i = 1; i <= N; i++){
        for(int j = 0; j <= sum; j++){
            if(j-app[i].S >= 0){
                dp[i][j] = max(dp[i][j], dp[i-1][j-app[i].S] + app[i].F);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }

문제의 점화식입니다.

sum은 N개 앱의 비용을 모두 더한 값입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321;

using namespace std;

int N, M, sum;
P app[101];
int dp[101][10001];

void solve(){
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= sum; j++){
            if(j-app[i].S >= 0){
                dp[i][j] = max(dp[i][j], dp[i-1][j-app[i].S] + app[i].F);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }
    for(int i = 1; i <= sum; i++){
        if(dp[N][i] >= M){
            cout << i;
            break;
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> app[i].F;
    }
    for(int i = 1; i <= N; i++){
        cin >> app[i].S;
        sum += app[i].S;
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요