BOJ 백준 7579 : 앱

시작하면서

　이번 문제는 배낭 알고리즘(Knapsack Algorithm) 과 관련된 문제이다.

BOJ 7579 - 앱

​

문제 이해

​ 이 문제는 배낭 알고리즘이라는 정해진 틀에서 해결하는 문제이다. 다음 링크에서 설명이 잘 되어 있으니 참고 바란다.

LINK

​

해결

#include <iostream>
#include <vector>
#include <limits.h>
#include <utility>

using namespace std;

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<vector<int>> dp;
    vector<int> usedMemoryByte, deactivationCost;
    int N, M;

    cin >> N >> M;

    usedMemoryByte.resize(N + 1);
    for (int i = 1; i <= N; i++)
    {
        cin >> usedMemoryByte[i];
    }

    int sum = 0;
    deactivationCost.resize(M);
    for (int i = 1; i <= N; i++)
    {
        cin >> deactivationCost[i];
        sum += deactivationCost[i];
    }

    int result = INT_MAX;
    dp.resize(N + 1);
    dp[0].resize(sum + 1);
    for (int i = 1; i <= N; i++)
    {
        dp[i].resize(sum + 1);
        for (int j = 0; j <= sum; j++)
        {
            dp[i][j] = dp[i - 1][j];

            if (j - deactivationCost[i] >= 0)
            {
                int compareValue = dp[i - 1][j - deactivationCost[i]] + usedMemoryByte[i];
                dp[i][j] = max(dp[i][j], compareValue);
            }

            if (dp[i][j] >= M)
            {
                result = min(result, j);                
            }
        }
    }

    cout << result;

    return 0;
}