백준 7579번 앱 [C++]

https://www.acmicpc.net/problem/7579

7579번: 앱

 

 

#문제 간단 정리

일단 배낭문제이다.

기존의 가방문제는 최소 무게를써서 최대 가치를 찾고

최대 가치를 가진 마지막 dp 배열이 정답이였다면

이 문제는 최소 비용으로 최대메모리를 찾고 그중에서 그 메모리이상의 첫번쨰 dp 배열을 찾는다는게 차이점

#문제 해결 방법

 

DP 배열을 dp[i][j]로 정의하고, 이를 "처음부터 i번째 앱까지 고려했을 때, 비활성화의 총 비용이 j일 때 확보할 수 있는 메모리의 최대량"으로 정의

즉 기존의 가방문제처럼 현재 비용(j)으로 구할수 있는 최대 메모리 dp[i][j]를 갱신한 후에

첫번째로 오는 M을 넘는 메모리를 가진 j(비용) 의 인덱스가 찾는 정답이다

쉽게 말하자면 dp 배열에는 순차적으로 j의 비용을 써서 얻는 최대 메모리가 저장되어있고

소비 j가 작으면서 M을 넘는 메모리의 허용량을 앞의 인덱스(작은j)부터 찾으면

 

즉 비용을 통해 최대 메모리를 가지도록 dp를 구현하고 최소 비용으로 목표 메리를 넘는 비용을 확인해 주면

된다는점이 기존 배낭문제랑 다르다.

 

 

#전체 코드

2차원 dp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll N, M;
    cin >> N >> M;

    vector<ll> m(N), c(N);
    for (ll& memory : m) cin >> memory;
    for (ll& cost : c) cin >> cost;

    ll sumCost = 0; // 가능한 최대 비용의 합
    for (int i = 0; i < N; i++) sumCost += c[i];

    vector<vector<ll>> dp(N+1, vector<ll>(sumCost+1, 0));

    // DP를 이용해 해결
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= sumCost; j++) {
            // 현재 앱 i를 비활성화하지 않는 경우
            dp[i][j] = dp[i-1][j];
            // 현재 앱 i를 비활성화할 수 있고, 그러기 위한 비용이 충분한 경우
            if (j >= c[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-c[i-1]] + m[i-1]);
            }
        }
    }

    // 필요한 메모리 M 바이트를 확보하기 위한 최소 비용 찾기
    ll answer = sumCost;
    for (int j = 0; j <= sumCost; j++) {
        if (dp[N][j] >= M) {
            answer = j;
            break;
        }
    }

    cout << answer << endl;

    return 0;
}

1차원dp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll N, M;
    cin >> N >> M;

    vector<ll> memory(N), cost(N);

    for (int i = 0; i < N; i++) {
        cin >> memory[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> cost[i];
    }

    ll maxCost = 100 * N; // 최대 비용
    vector<ll> dp(maxCost+1, 0); // 비용에 따른 메모리 최대치 저장

    for (int i = 0; i < N; i++) {
        for (int j = maxCost; j >= cost[i]; j--) {
            dp[j] = max(dp[j], dp[j-cost[i]] + memory[i]);
        }
    }

    // 필요한 메모리 M 바이트를 확보하기 위한 최소 비용을 찾기
    ll answer = maxCost;
    for (int i = 0; i <= maxCost; i++) {
        if (dp[i] >= M) {
            answer = i;
            break;
        }
    }

    cout << answer << endl;

    return 0;
}