[백준 7579] - 앱(C++)[골드3]

문제

우리는 스마트폰을 사용하면서 여러 가지 앱(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 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다. 

 

🔎문제 풀이

문제를 읽어보시면 배낭 문제와 굉장히 유사한 점이 많다는 것을 DP문제를 풀어보셨다면 느꼈을 겁니다.
배낭 문제는 물건 개수, 배낭 최대 무게가 있고, 
해당 문제는 앱 개수,  목표 메모리가 있습니다.
우리는 최대무게와 목표 메모리를 향해 과정을 진행하면서 배낭은 이익을 최대로 , 앱은 비용을 최소로 하는 문제입니다.

 

따라서 해당 문제도 배낭과 유사하게 2차원 배열을 N * M 배열로 선언하려고 했는데, 

input의 최대크기가 어마어마했습니다.

N은 최댓값이 100 -> 10^2, M은 10,000,000 -> 10^7 

그러면 이제 메모리의 크기는 4*10^9 byte  이므로 128MB(128 * 10^6)를 매우 매우 뛰어넘고도 남는 사이즈라서

아마 메모리 초과가 뜰 것입니다.

그렇다면 배열 크기에 대한 접근법을 다시 생각해봐야 합니다.

그래서 저는 배열의 크기를 N*cost의 총합으로 했습니다.  그리고 배열에 들어가는 값은 앱의 메모리가 될 것입니다.

이렇게 된다면 메모리 초과를 신경 쓸 필요가 없어집니다.

dp [N][cost] = memory

 

테스트케이스를 기준으로 예시를 들어서 설명하겠습니다. 

우선 저는 메모리가 크고, 비용이 작은 순서대로 앱을 정렬했습니다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
10/0	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
30/3	10	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
40/4	10	10	10	40	50	50	50	80	80	80	80	80	80	80	80	80
35/5	10	10	10	40	50	50	50	80	80	85	85	85	115	115	115	115
20/3	10	10	10	40	50	50	60	80	80	85	85	85	115	115	115	135

열은 몇 번째 앱인지를 뜻하고, 행은 비용을 뜻합니다.

만약 행이 해당 앱의 비용보다 작다면 이전상태의 값이 들어가게 됩니다.

행이 해당 앱의 비용보다 크거나 같다면 이전상태의 값 vs 이전상태에서 비용을 뺀 상태 + 해당 메모리값 중 최댓값이 들어가게 됩니다.

음 이게 말이 굉장히 어려운데 예시를 들면 무슨 느낌인지 아실 겁니다.

 

해당 번호가 메모리가 업데이트 일어난 상황입니다.

화살표가 아래로 내려간 경우는 앱을 종료시키지 않은 상황이고, 대각선으로 이동한 경우는 앱을 종료시킨 상황입니다.

1번의 경우 cost를 4까지 사용할 수 있어서 1번앱과 2번앱을 둘다 종료시키고 40의 메모리를 얻은 상황입니다.

6번의 경우 cost를 6까지 사용할수 있어서 1번 앱, 2번 앱, 6번 앱을 종료시키고, 60의 메모리를 얻은 상황입니다.

우리는 위 배열에서 목표 메모리인 M값을 넘고, 최소의 cost를 찾아야 하기에, 최소 cost인 6이라는 값을 얻을 수 있습니다.

 

💻코드

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int n,m;
vector<int>a;
vector<int>c;
int dp[101][10001]={0,};
void sort_app();
void funct();
int main(){
    cin>>n>>m;
    a.resize(n+1,0);
    c.resize(n+1,0);
    for(int i=1; i<=n;i++){
        cin>>a[i];
    }
    for(int i=1; i<=n;i++){
        cin>>c[i];
    }
    sort_app(); //비용이 작고 단위메모리가 큰 순서대로 정렬함.
    funct();
    for(int i=0; i<=10000;i++){
        if(m<=dp[n][i]){ //메모리가 충족일때 가장 작은 cost를 반환해야함. 따라서 가장 처음 만나게 되는 i값이 그때의 최소비용일 것이다.
            cout<<i<<endl;
            break;
        }
    }
}
void sort_app(){ //비용이적고 앱크기가 큰 순서대로 정렬한다.
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            if(c[i]==0){
                continue;
            }
            if(c[j]==0){ //추가 비용이 0인 앱은 가장 앞으로
                swap(a[i],a[j]);
                swap(c[i],c[j]);
                continue;
            }
            if(a[j]/c[j] > a[i]/c[i]){ //단위메모리가 큰 앱이 앞으로
                swap(a[j],a[i]);
                swap(c[j],c[i]);
            }
            /*
            else if(a[j]/c[j]==a[i]/c[i]){ //만약 같다면. 메모리가 작은게 앞으로.
                if(a[j]<a[i]){ 
                    swap(a[j],a[i]);
                    swap(c[j],c[i]);
                }
            }
            */
        }
    }
}
void funct(){
    for(int i=1; i<=n; i++){
        for(int j=0; j<=10000;j++){
            int memory = a[i], cost = c[i];
            if(j<cost) //현재 단계에서 못담는다.
                dp[i][j]=dp[i-1][j];
            else if(j>=cost)
                dp[i][j]= max(dp[i-1][j],dp[i-1][j-cost]+memory); //무조건 메모리 값이 큰 걸 넣어줘야함. 그리고 cost가 작아야함
        }
    }
}

 

😀느낀 점

• 메모리와 시간 복잡도는 항상 주의 깊게 보자.
  • 최악의 상황에서의 메모리를 계산해서 코드를 지웠다가 다시 짜는 상황은 다시는 없게 만들 ja...
• 다른 배낭문제와는 차별화된 점이 있어서 신선했다.