[백준] 7579 앱 (C++)

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

7579번: 앱

문제

우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.

하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다.

메모리 부족 상황에서 활성화 되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화 하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다

현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

입력

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다

단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.

출력

필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.

---

풀이

'평범한 배낭' 문제와 비슷한 문제이다.

평범한 배낭 문제에서는 가방 안에 최대로 담을 수 있는 가치의 총합을 출력하여 MAX를 반복해나갔다면

이 문제에서는 최소의 비용을 출력해야 하기 때문에 MIN을 반복해나가는 문제이다.

 

그런데 문제가 있다. 앱은 100개이고, 메모리의 최댓값이 10,000,000이다.

평범한 배낭 문제처럼 1~10,000,000까지의 메모리 각각의 최소 비용을 저장하려고 하면

100 * 10,000,000 의 2차원 배열이 필요하고 메모리 초과가 발생한다.

실제로 아래 코드를 제출한 결과는 다음과 같다.

 

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

#define MAX_COST 10000001

int apps[101][2];
vector<int> dp[101];

void reset(int n, int m){
    for (int j = 0; j <= m; j++){
        dp[0].push_back(MAX_COST);   
    }
}

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

    int n, m;
    cin >> n >> m;
    reset(n, m);
    
    // 메모리를 입력받음
    for (int i = 1; i <= n; i++){
        cin >> apps[i][0];
    }
    // 비용을 입력받음
    for (int i = 1; i <= n; i++){
        cin >> apps[i][1];
    }

    // 배낭 문제와 비슷하다
    for (int i = 1; i <= n; i++){
        int memory = apps[i][0];
        int cost = apps[i][1];
        for (int j = 0; j <= memory; j++){
            dp[i].push_back(min(dp[i-1][j], cost));
        }
        for (int j = memory+1; j <= m; j++){
            dp[i].push_back(min(dp[i-1][j], dp[i-1][j-memory]+cost));
        }
    }

    cout << dp[n][m];
}

 

이에 메모리를 확보하기 위하여 앱 메모리 값을 map에 넣고 효율적으로 관리하는 것을 시도해보았다.

하지만 map을 활용한 코드도 시간 초과가 발생하였다.

 

#include <iostream>
#include <vector>
#include <climits>
#include <map>
using namespace std;

int apps[101][2];
map<int, int> dp;

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

    int n, m;
    cin >> n >> m;
    
    // 메모리를 입력받음
    for (int i = 1; i <= n; i++){
        cin >> apps[i][0];
    }
    // 비용을 입력받음
    for (int i = 1; i <= n; i++){
        cin >> apps[i][1];
    }

    // 배낭 문제와 비슷하다. 그런데 같은 방식으로 풀면 메모리 초과로 map을 사용하여 풂
    int answer = INT_MAX;
    for (int i = 1; i <= n; i++){
        int memory = apps[i][0];
        int cost = apps[i][1];
        
        // memory가 m보다 크다면 map에 넣을 필요가 없음
        if (memory >= m){
            answer = min(answer, cost);
            continue;
        }

        int dpSize = dp.size();
        auto it = dp.begin();
        for (int j = 0; j < dpSize; j++, it++){
            int target = it->first + memory;
            // 만약 target이 m보다 크다면 map에 넣을 필요가 없음
            if (target >= m){
                answer = min(answer, it->second+cost);
            }
            else{
                // dp에 찾고자 하는 값이 있는 경우
                if (dp.find(target) != dp.end()){
                    dp[target] = min(dp[target], it->second + cost);
                }
                // 찾고자 하는 값이 없는 경우 새로 insert
                else{
                    dp.insert({target, it->second + cost});
                }
            }

        }    
        // map에 반영
        if (dp.find(memory) != dp.end()){
            dp[memory] = min(dp[memory], cost);
        }
        else{
            dp.insert({memory, cost});
        }
    }
    
    cout << answer;
}

 

결국 이 방법으로는 문제를 풀 수 없다 생각하고 접근을 다르게 하였다.

메모리의 최댓값은 10,000,000으로 매우 크지만 비용의 최댓값은 100 × 100 = 10,000으로 상대적으로 매우 적었다.

이에 각 비용별로 최대로 저장할 수 있는 메모리의 크기를 저장하였다.

예제 1번의 dp테이블은 다음과 같다.

 

코드

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

int n, m;
int apps[101][2];
int dp[101][10001];

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

    int n, m;
	cin >> n >> m;

    // 메모리를 입력받음
	for (int i = 1; i <= n; i++){
        cin >> apps[i][0];
    }
    // 비용을 입력받으면서 비용의 총합을 저장
    int totalCost = 0;
	for (int i = 1; i <= n; i++) {
		cin >> apps[i][1];
		totalCost += apps[i][1];
	}

	for (int i = 1; i <= n; i++){
        for (int j = 0; j < apps[i][1]; j++){
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
		for (int j = apps[i][1]; j <= totalCost; j++){
			dp[i][j] = max(dp[i-1][j], dp[i-1][j - apps[i][1]] + apps[i][0]);
		}
	}

	for (int i = 0; i <= totalCost; i++){
		if (dp[n][i] >= m){
			cout << i;
			return 0;
		}	
	}
}