[백준/C++] 7579번 앱

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

7579번: 앱

 

 

문제 분석

새로운 앱을 활성화하기 위해서 기존에 활성화 된 앱들을 종료해 메모리를 확보하는 문제입니다. 앱을 종료할 때 고려할 사항으로는 앱이 차지하는 메모리와 앱을 종료했을 때 발생하는 비용이 있습니다. 새로운 앱을 활성화 할 수 있을 만큼 충분한 메모리를 확보하면서 비용은 최소화하는 것이 목적입니다.

일종의 배낭 문제로, 다이나믹 프로그래밍을 활용해 문제를 해결할 수 있습니다. 얼핏 보기에 메모리가 배낭의 크기와 개념이 비슷해서 메모리를 배낭의 크기로 생각하고 접근하기 쉽지만, 메모리는 10,000,000칸이나 되어 시간 복잡도가 굉장히 높고, 비용을 최소화 하면서 충분한 메모리를 확보하는 알고리즘을 구현하기 어렵습니다.

더 좋은 방법은, 비용을 배낭의 크기로 생각하는 것입니다. 앱의 갯수가 100개, 각 앱의 최대 비용이 100이므로 비용의 총 합은 10,000을 넘어가지 않습니다. 따라서 앱의 갯수*비용의 총합인 1,000,000번의 연산 안에 문제를 해결할 수 있습니다.

 

코드

#include<iostream>

using namespace std;

int N, M;
int dp[10001];
int A[101];
int c[101];

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

	cin>>N>>M;

	for (int i=1; i<=N; i++)
		cin>>A[i];

    for(int i=1; i<=N; i++)
        cin>>c[i];

    for (int i=1; i<=N; i++) //앱 번호
    {
        for (int j=10000; j>0; j--) //비용
        {
        	//j 만큼의 비용으로 확보할 수 있는 최대 메모리를 계산합니다.
            if (j>=c[i]) dp[j] = max(dp[j], dp[j - c[i]] + A[i]);
        }
    }

    int cost=0;

    while(dp[cost]<M) cost+=1; //M이상의 메모리를 확보할 수 있는 최소 비용을 찾음

    cout<<cost;

    return 0;
}

 

문제 풀이

0-1 배낭 문제와 동일한 알고리즘을 활용합니다. 배낭의 크기=앱의 비용, 물건의 가치=앱을 정리했을 때 확보되는 메모리라고 생각하고 구현합니다. 0-1 배낭 문제와 다른점은 배낭의 크기가 정해져있지 않습니다. 따라서 비용의 상한값인 10,000까지 계산합니다. 그렇다면 0부터 10,000까지 주어진 비용으로 확보할 수 있는 최대 메모리를 모두 알아낼 수 있습니다. 계산을 끝내고, 비용이 0일때부터 비용을 1씩 늘려가며 필요한 메모리 이상을 확보할 수 있는 최소 비용을 찾으면 문제는 해결됩니다.