백준/7579번/앱/골드3

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

문제 설명

Site: Baekjoon
Number: 7579
Category: Dynamic Programming
Rank: Gold 3

프로그램 별 주어진 메모리 m과 코스트 c가 있으며 c를 최소화 하여 M만큼의 메모리를 확보해야하는 문제이다.

주의점 M의 최대 크기가 10,000,000이기 때문에 기존의 DP처럼 M의 크기별 최소 cost를 구한다면 dp배열의 크기로 인해 메모리 초과가 발생한다.

반대로 cost별 최소 메모리를 구하여 풀이를 진행해야 한다.

cost수치 별 가능한 최소 메모리를 구하며 지속적으로 min연산을 통해 계산한다.

#include <iostream>
#include <vector>

#define PII pair<int, int>

using namespace std;

int dp[101][10000];
PII Programs[101];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < N; i++)
    {
        int mem;
        cin >> mem;

        Programs[i].first = mem;
    }

    for(int i = 0; i < N; i++)
    {
        int cost;
        cin >> cost;

        Programs[i].second = cost;
    }

    int leastCost = 10000001;
    for(int i = 0; i <= 10000; i++)
    {
        if (Programs[0].second > i)
            continue;

        dp[0][i] = Programs[0].first;
    }

    if (Programs[0].first >= M)
        leastCost = Programs[0].second;

    for(int i = 1; i < N; i++)
    {
	    for(int j = 0; j <= 10000; j++)
	    {
            if (Programs[i].second > j)
            {
                dp[i][j] = dp[i - 1][j];
                continue;
            }

            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Programs[i].second] + Programs[i].first);
            if (dp[i][j] >= M)
                leastCost = min(leastCost, j);
	    }
    }

    cout << leastCost;

    return 0;
}