[c++] BOJ 7579 :: 앱

문제

[앱 문제 바로가기]

7579번: 앱

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

 

풀이

우선 n이라는 입력 값이 100의 범위로 크지 않기 때문에 brute force를 적용한다. 하지만 최대한 시간을 줄여야 하는데 시간을 줄이기 위해서는 메모이제이션을 이용한 dp를 적용하면 된다.

 

 첫번째 방법. 특정 메모리(target)가 남았을 때, 현재까지 끈 어플(visited)들이 같다면 그에 따른 최소비용이 같다. 메모이제이션을 (target, visited) => cost 로 진행하였다. 하지만 visited(몇번째 index 들을 들렀는지)를 간단히 나타내기가 쉽지 않다.

 두번째 방법. 배낭 문제처럼 생각하여 순차적으로 앱을 훑어보면서 현재 index에서 앱을 켰을 때의 최소 비용과 앱을 키지 않았을 때의 최소비용을 비교한다. 순차적으로 진행하기 때문에 특정 메모리(target)가 남았을 때 현재 index에서 어플을 켜는지 안 켜는지에 따른 최소비용은 같다. 메모이제이션을 (target, index) => cost로 하였다. 하지만 메모리 초과가 난다.

 세번째 방법. 메모리 초과가 나지 않기 위해서는 target이라는 10,000,000 범위의 입력을 메모이제이션의 차원으로 취급해서는 안된다. 따라서 cost라는 100 범위의 입력을 메모이제이션에 이용할 수 있도록 생각을 바꿔야 한다. 특정 index의 앱을 키거나 끌 때 특정 cost가 발생하며 해당 cost에 따른 최대의 메모리는 같다. 따라서 (index, cost) => memory 로 진행하였다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

vector<int> memoryList;
vector<int> costList;
int memo[10001]; // cost에서 최대 메모리

int main() {
	int N; int M; cin >> N >> M; // 10^7
	int sum = 0;
	
	for(int i=0; i<N; i++){
		int tmp; cin >> tmp;
		memoryList.push_back(tmp);
	}
	for(int i=0; i<N; i++){
		int tmp; cin >> tmp;
		costList.push_back(tmp);
		sum+= tmp;
	}
	
	for(int i=0; i<N; i++){
		for(int j=sum; j>=costList[i]; j--){
			memo[j] = max(memo[j], memo[j-costList[i]]+memoryList[i]);
		}
	}
	
	int i=0;
	while(memo[i] < M){
		i++;
	}
	cout << i << '\n';
	
}

 

결과