백준 7579 - 앱 (C++)

 

 

 

N개의 앱이 켜있다고 해보자.

 

각 앱은 m_1, m_2, m_3....m_n의 메모리를 사용하고 있으며, 각 앱을 비활성화하게 되면 각 c_1, c_2, c_3, c_4...c_n의 비용이 발생하게 된다.

 

M바이트를 확보하기 위해, 임의의 앱을 비활성화 했을 때 발생하는 비용의 최소값을 구하자.

 

문제 풀이

문제 자체는 간단한 배낭 문제이다. 다만, 일반적인 배낭 문제와는 다르게 최소값을 구하는 문제이기 때문에 떠올리는 것이나 구현하는 것이 다소 어려울 수도 있었을 것 같다.

 

배낭문제는 보통 개수와 수치(무게, 비용 등)을 이용해서 2차원 배열을 구성하게 된다. 위의 문제에서 개수, 메모리를 이용해서 2차원 배열을 구성하게 되면 최대 1000000000개의 원소를 가지는 배열을 만들어야 하므로 메모리 초과가 발생할 수 밖에 없다. 그러므로 2차원 배열은 (개수, 비용)을 이용해서 구성할 것이다.

 

그렇다면, 배열의 원소는 어떤 값을 저장해야 할까?

문제에서 구하는 것은 M바이트를 확보하기 위한 최소 비용이다.

 

반대로, N의 비용을 사용했을 때 최대한으로 확보할 수 있는 메모리를 구하면 어떨까?

문제에서 주어진 최대 비용은 10000이다. (100개의 앱 * 100의 비용)

 

그러므로, N의 비용을 사용했을 때 최대한으로 확보할 수 있는 메모리를 배열에 저장한 뒤 0 ~ 10000 까지의 비용 중 확보할 수 있는 메모리가 입력값보다 큰 비용을 구한 뒤, 그 값의 최소를 출력하면 되는 것이다.

 

배열의 원소를 갱신하는 것은 일반 배낭 문제와 동일하게 하면 된다.

 

풀이 코드

int NumApp = 0;
int TargetMem = 0;

std::cin >> NumApp >> TargetMem;

std::vector<int> AppMemories(NumApp + 1, 0);
std::vector<int> AppCosts(NumApp + 1, 0);

for (int i = 1; i <= NumApp; i++)
{
    std::cin >> AppMemories[i];
}

for (int i = 1; i <= NumApp; i++)
{
    std::cin >> AppCosts[i];
}

먼저, 입력을 모두 받아주자.

앱의 개수와 확보할 메모리를 입력받은 뒤, 각 앱의 메모리 사용량과 비활성화시 발생하는 비용을 모두 저장해주었다.

std::vector<std::vector<int>> DP(NumApp + 1, std::vector<int>(10001, 0));

다음으로 배낭 문제 해결에 사용할 DP 배열을 만들어주었다.

발생할 수 있는 최대 비용은 10000이므로, 배열의 size를 위와 같이 만들어주었다.

for (int i = 1; i <= NumApp; i++)
{
    for (int j = 0; j <= 10000; j++)
    {
        if (j >= AppCosts[i])
        {
            DP[i][j] = std::max(DP[i - 1][j], DP[i - 1][j - AppCosts[i]] + AppMemories[i]);
        }
        else
        {
            DP[i][j] = DP[i - 1][j];
        }
    }
}

일반적인 배낭문제와 동일하게 반복문을 돌려주면 된다.

각 원소의 값은 i개의 앱을 비활성화하여 j의 비용이 발생했을 때 확보할 수 있는 최대 메모리양이다.

int Answer = 0;

for (int i = 0; i <= 10000; i++)
{
    if (DP[NumApp][i] >= TargetMem)
    {
        Answer = i;
        break;
    }
}

이후, i를 0부터 10000까지 반복문을 돌며 TargetMem을 확보할 수 있는 최소 비용을 구해주면 된다.

std::cout << Answer;

답을 출력해주면 된다.

 

 

코드 전문

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumApp = 0;
    int TargetMem = 0;
    
    std::cin >> NumApp >> TargetMem;

    std::vector<int> AppMemories(NumApp + 1, 0);
    std::vector<int> AppCosts(NumApp + 1, 0);

    for (int i = 1; i <= NumApp; i++)
    {
        std::cin >> AppMemories[i];
    }

    for (int i = 1; i <= NumApp; i++)
    {
        std::cin >> AppCosts[i];
    }

    std::vector<std::vector<int>> DP(NumApp + 1, std::vector<int>(10001, 0));

    for (int i = 1; i <= NumApp; i++)
    {
        for (int j = 0; j <= 10000; j++)
        {
            if (j >= AppCosts[i])
            {
                DP[i][j] = std::max(DP[i - 1][j], DP[i - 1][j - AppCosts[i]] + AppMemories[i]);
            }
            else
            {
                DP[i][j] = DP[i - 1][j];
            }
        }
    }

    int Answer = 0;

    for (int i = 0; i <= 10000; i++)
    {
        if (DP[NumApp][i] >= TargetMem)
        {
            Answer = i;
            break;
        }
    }

    std::cout << Answer;

    return 0;
}