[JAVA]앱(Baekjoon)

문제

문제

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

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

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

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

입력

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

 단, $1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000$이며, $1 ≤ m_1, ..., m_N ≤ 10,000,000$을 만족한다. 또한, $0 ≤ c_1, ..., c_N ≤ 100$이고, $M ≤ m_1 + m_2 + ... + m_N$이다.

출력

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

 

예제 입력 1

5 60
30 10 20 35 40
3 0 3 5 4

예제 출력 1

6

풀이

 문제를 보고 Branch and Bound 알고리즘을 떠올렸다. 지난 주, 11779번_최소_비용_구하기_2를 풀었을 때도 사용했었던 알고리즘이다. 그러나 아직 체화는 되지 않아서 1학기에 들었던 알고리즘 강의 자료를 참고하여 작성하였다.

 노드들로 구성된 트리구조이다. Level당 하나의 아이템이 해당된다. 노드는 memory, cost, level, bound를 멤버 변수로 가진다. memory는 현재 노드에서 반환된 메모리 총 양, cost는 종료된 프로세스들을 다시 활성화시키기 위한 총 비용, level은 아이템을 가리키는 인덱스로 사용되고, bound는 하위 노드들을 모두 포함하여 볼 때 cost의 최솟값이다.
 level 0의 노드는 초기 노드이다. bound함수를 통해 구한 bound는 5이다. bound를 구할 때는 $c_i/m_i$를 이용하여, 메모리 M을 반환받기 위한 cost의 최솟값을 구하였다.
 각 level에 해당되는 아이템들은 $c_i/m_i$를 계산하여 오름차순으로 정렬하여 순서대로 level에 배치시킨다. 따라서, level 1에 해당되는 아이템은 $c$가 0인 아이템이 해당된다. 부모 노드로부터 왼쪽 자식 노드는 포함(1), 오른쪽 자식 노드는 불포함(0)으로 나뉜다. 자식 노드들의 bound와 memory cost를 초기화한다.
 우선순위 큐를 이용하여 bound를 기준으로 오름차순으로 하여 우선순위를 매긴다. 따라서, bound가 가장 작은 노드가 poll되게 되고, 그 노드에서 계속 자식 노드들을 만들고 큐에 넣게 된다. 큐에 넣는 조건은 bound가 min_cost라는 변수보다 작을 때이다. 그리고, 노드의 memory 변수가 M보다 크거나 같게 되면 그 노드는 더 이상 자식을 만들지 않는다.(큐에 삽입되지 않음) 그리고 cost값이 min_cost보다 작다면 min_cost값을 갱신한다.
 처음에는 77퍼센트에서 메모리 초과가 발생하였다. 곰곰히, 생각해보니 아이템 개수가 N이라면 leaf node의 개수는 $2^N$이 된다. 결론적으로는 우선순위 큐의 사이즈가 최악의 경우 $2^N$이라는건데, 메모리 초과가 발생한다면 이 부분에서 발생하지 않을까라는 생각이 들어, 우선순위 큐의 크기가 20을 넘는다면 20이 될 때까지 poll을 반복했다. 그때는 틀렸다고 답이 나와서 조건문을 20에서 200으로 바꾸었더니 정답처리되었다. 근데, 지금 생각해보면 poll이 아니라 큐의 tail에서 노드들을 빼야한다. 왜냐하면, poll을 하게 되면 큐의 head에서 빠지는데, 이 노드는 정답에 유력한 노드이기 때문이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class node_7579 implements Comparable<node_7579>{
    int memory;
    int cost;
    float bound;
    int level;
    node_7579(){}
    node_7579(int memory, int cost, int level){
        this.memory = memory;
        this.cost = cost;
        this.level = level;
    }
    node_7579(int memory, int cost, float bound, int level){
        this.memory = memory;
        this.cost = cost;
        this.bound = bound;
        this.level = level;
    }
    //node간 비교, 정렬 시 사용되는 compareTo 오버라이딩
    @Override
    public int compareTo(node_7579 target){
        return this.bound <= target.bound ? -1 : 1;
    }
}

class item_7579 implements Comparable<item_7579>{
    int memory;
    int cost;
    item_7579(int memory, int cost){
        this.memory = memory;
        this.cost = cost;
    }
    //어플간 비교, 정렬 시 memory/cost를 이용해 오름차순으로 정렬
    @Override
    public int compareTo(item_7579 target){
        if((float)this.memory / (float)this.cost == (float)target.memory / (float)target.cost)
            return target.memory - this.memory;
        return (float)this.memory / (float)this.cost <= (float)target.memory / (float)target.cost ? 1 : -1;
    }
}

public class _7579 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static PriorityQueue<node_7579> queue = new PriorityQueue<>();
    static int[] memory;
    static int[] cost;
    static final int INF = 10_000_000;  //무한대 상수
    static int M, N;

    public static void main(String[] args) throws Exception{
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        //메모리값 입력
        memory = new int[N+1];
        for(int i = 1; i <= N; i++)
            memory[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        //비용값 입력
        cost = new int[N+1];
        for(int i = 1; i <= N; i++)
            cost[i] = Integer.parseInt(st.nextToken());
        //우선순위 큐를 이용해 아이템 정렬 및 재할당
        PriorityQueue<item_7579> tmp_queue = new PriorityQueue<>();
        for(int i = 1; i <= N; i++)
            tmp_queue.add(new item_7579(memory[i], cost[i]));
        for(int i = 1; i <= N; i++){
            item_7579 tmp = tmp_queue.poll();
            memory[i] = tmp.memory;
            cost[i] = tmp.cost;
        }
        tmp_queue = null; //가비지 컬렉터
        node_7579 u, v;
        int min_cost = INF;
        //초기 노드(level 0) 할당 및 우선순위 큐 삽입
        v = new node_7579(0, 0,  0);
        u = new node_7579();
        v.bound = bound(v);
        queue.add(v);
        while(!queue.isEmpty()){
            /////메모리초과로 인해 추가한 코드///////
            while(queue.size() > 200)
                queue.poll();
            /////////////////////////////////////////
            v = queue.poll();
            //우선순위 큐에서 꺼낸 노드의 bound가 min_cost보다 크다면
            //그 노드 및 하위 노드들은 고려할 필요가 없음
            if(v.bound < min_cost){
                u.level = v.level + 1;
                ///////////////LEFT CHILD : included item_7579 case/////////////
                u.cost = v.cost + cost[u.level];
                u.memory = v.memory + memory[u.level];
                //비용이 min_cost보다 작고, 메모리를 M 이상 반환한다면 min_cost 갱신
                if(u.cost < min_cost && u.memory >= M)
                    min_cost = u.cost;
                u.bound = bound(u);
                //bound가 0이라면 leaf node이거나 메모리를 M이상 반환함
                if(u.bound < min_cost && u.bound != 0)
                    queue.add(new node_7579(u.memory, u.cost, u.bound, u.level));

                //////////RIGHT CHILD : not included item_7579 case/////////////
                u.cost = v.cost;
                u.memory = v.memory;
                u.bound = bound(u);
                if(u.bound < min_cost && u.bound != 0)
                    queue.add(new node_7579(u.memory, u.cost, u.bound, u.level));
            }
        }
        System.out.println(min_cost);
    }

    //bound구하는 함수
    public static float bound(node_7579 u){
        int j;
        float result;
        int total_memory;
        //메모리를 M이상 반환한다면 leaf node
        if(u.memory >= M)
            return 0;
        result = u.cost;
        total_memory = u.memory;
        j = u.level + 1;
        //하위 아이템들을 포함시켜 bound 갱신
        while(j <= N && total_memory + memory[j] < M){
            result += cost[j];
            total_memory += memory[j++];
        }
        //leaf node인데 메모리를 M이상 반환하지 못하는 노드
        if(j > N && total_memory < M)
            return 0;
        //하위 아이템을 분할 계산하여 bound 갱신
        if(j <= N && cost[j] != 0)
            result += (M - total_memory) * (float)cost[j] / (float)memory[j];
        return result;
    }
}

 추가적으로 다른 사람이 DP기법으로 푼 알고리즘이 있어 첨부한다. 본 문제의 의도가 아마 DP인것같은데, 풀이가 깔끔하다.

 cost의 최대 값이 10,000이므로 배열의 크기를 10,0001로 설정한다. 업데이트를 할때 값이 겹치지 않도록 뒤에서부터 확인해야 한다. 배열의 값이 -1이면 이전 cost에 더해질 필요가 없으므로 무시한다. 그렇지 않다면 cost만큼 뺀 이전 배열 값에서 현재 memory값을 더한 것이 더 크다면 update 해준다. 초기화를 위해 메모리값이 -1인 경우 update 해준다(base).

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[] memories = new int[N];
int[] costs = new int[N];
for(int i = 0; i < N; i++)
    memories[i] = Integer.parseInt(st.nextToken());
for(int i = 0; i < N; i++>)
    costs[i] = Integer.parseInt(st.nextToken());

// dp 배열 초기화
int[] dp = new int[10001];
Arrays.fill(dp, -1);

// dp[i]: i cost를 써서 확보할 수 잇는 최대 메모리
for(int i = 0; i < N; i++){
    int cost = costs[i];
    // 뒤에서부터 확인해야 겹치지않고 값을 update할 수 있다.
    for(int j = 10000; j >= cost; j--){
        if(dp[j-cost] != -1){
            // 이전 j-cost 까지의 최대값에 현재 mem을 더하는게 더 크다면 update
            if(dp[ j - cost ] + memories[i] > dp[j])
                dp[j] = dp[j-cost] + memories[i];
        }
    }
    // 메모리 업데이트가 안되어있는 경우 업데이트
    // 단 메모리가 더 큰 경우에만 업데이트 가능
    if(dp[cost] < memories[i])
        dp[cost] = memories[i];
}