문제
우리는 스마트폰을 사용하면서 여러 가지 앱(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 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.
풀이
문제가 길지만 간단히 요약하자면
N개 이하의 물건을 사용해서 M의 무게를 최소비용으로 맞추는 문제이다.
당연하지만 물건 하나하나를 생각해주는 경우는 2^N의 시간이 걸리기 때문에 완전탐색으로는 풀 수 없다.
그렇다면 다른 알고리즘을 사용해야되는데, 처음에는 priority_queue를 이용한 그리디 방법을 생각해보았다.
하지만 이 문제에서는, 단순히 M보다 작아야 하는 것이 아니라 각각의 앱 마다 만들 수 있는 모든 무게의 경우를 따져줘야 비용의 최솟값을 구할 수 있기 떄문에 pq는 적합하지 않다는 생각이 들었다.
그러므로, 모든 앱에따른 메모리에 변화와 그에따른 비용의 변화를 모두 확인해야 하기 때문에 DP 로 구상하였다.
for(int i=1; i<=N; i++){
sum_m += arr[i][0];
for(int j=1; j<=sum_m; j++){
cparr[j] = dp[j];
if(j > 10000000) break; //1
if(j <= arr[i][0]) dp[j] = min(cparr[j], arr[i][1]); //2
else dp[j] = min(cparr[j-arr[i][0]]+arr[i][1], cparr[j]); //3
}
}우선 이 DP코드는 앱을 기준으로 메모리에 대한 반복문을 돌린 것이다.
sum_m은 앱을 체크할때마다 늘어나는, 모든 앱을 사용해서 만드는 메모리의 누적합을 나타낸다.
//1
Mi가 10,000,000 이하이기 때문에 모든 앱의 메모리의 합이 구하고자 하는 M을 넘을 수 있기 때문에 j가 10,000,000 이하인 경우만 체크해 주도록 하였다.
/2
j가 특정 앱의 메모리보다 작은 경우는 이 앱을 쓰지 않고 이전의 앱들만 사용해서 얻는 최선의 결과, 이 앱만을 사용해서 얻는 결과 중 작은 것을 선택하도록 했고
//3
j가 특정 앱의 메모리보다 큰 경우는 이 앱을 사용하기 위해 이 앱을 사용하지 않고 이 앱의 메모리만큼 빼준 배열의 값, 이 앱을 사용하지 않은 경우의 값 중 작은 것을 택하도록 했다.
주의
처음에 DP배열 자체를 int형 101 * 10,000,000 이차원 배열로 생성했다가 너무 큰 배열때문에 컴파일 에러가 떴다.
그러므로 따로 int형 1 * 10,000,000 배열 cparr을 생성하여 특정 물건을 사용하기 이전의 DP 결과를 항상 저장해 놓을 수 있도록 하였다.
정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int N,M, arr[101][2], dp[10000001], cparr[10000001];
int main(){
cin>>N>>M;
for(int i=1; i<=N; i++)
cin>>arr[i][0];
for(int i=1; i<=N; i++)
cin>>arr[i][1];
for(int i=0; i<=M; i++)
dp[i] = INF;
int sum_m = 0;
for(int i=1; i<=N; i++){
sum_m += arr[i][0];
for(int j=1; j<=sum_m; j++){
cparr[j] = dp[j];
if(j > 10000000) break;
if(j <= arr[i][0]) dp[j] = min(cparr[j], arr[i][1]);
else dp[j] = min(cparr[j-arr[i][0]]+arr[i][1], cparr[j]);
}
}
cout<<dp[M];
}