[백준 7579] 앱

 

어려웠던 부분

1. 처음 생각했던 풀이
   
   1. 그리디
      - 처음에는 최소한의 비용으로 메모리 M이상을 확보하면 된다고 생각했다. 그래서 앱을 비용으로 오름차순 정렬하고 동일한 비용일 때는 메모리로 내림차순 정렬한 후에 앞에서 부터 하나씩 비활성화 하면서 메모리 M이상을 확보하면 답이라고 생각했다.
      하지만 이렇게 문제를 푼다면, 비활성화 하는데에 필요한 비용이 더 큰 앱 하나를 종료할 때가 답인 경우가 있다.
      
      

앱	메모리	비용
A	6	1
B	6	1
C	100	3

위의 경우, 필요한 메모리가 100인 경우, 앱 C 하나만 종료하면 필요한 메모리를 모두 확보할 수 있으므로 답은 3이다. 하지만, 내가 생각한 그리디로 문제를 푼다면 5가 나온다.

 

그래서 이 문제는 배낭 알고리즘으로 접근해야 한다.

다만, 배낭 알고리즘에서는 배낭에 물건을 담아 최대한의 가치를 구하는 알고리즘인데 이 문제에서는 '앱을 비활성화 하는데에 필요한 비용'을 '배낭에 담을 수 있는 최대 무게' 로 생각해야 한다. 그리고 '앱을 비활성화하여 얻을 수 있는 메모리'를 '배낭에 담은 물건의 가치'로 생각해서 풀어야 하는 문제이다.

 

풀이

이 문제는 비용을 1씩 증가하면서 앱을 비활성화하여 얻을 수 있는 메모리를 구하는 방법으로 접근하면 된다.
(배낭 알고리즘은 배낭의 무게를 1씩 증가하면서 물건을 담아 최대 가치를 구하는 알고리즘이다.)

 

여기서 사용하는 dp[i][c]의 의미는 비용 c를 허용했을 때, i번째 앱 내에서 비활성화 하여 얻을 수 있는 메모리의 최대값 이다.

 

현재 허용하는 비용보다 앱을 비활성화하는데에 필요한 비용이 더 큰 경우 현재 앱을 비활성화하지 못한다.(왜냐하면, 비용 3까지만 허용했는데 현재 앱을 비활성화하는데 필요한 비용이 5라면 비용이 부족하니까)
이때는 이전의 앱까지 고려했을때 얻을 수 있는 메모리와 동일하다. 이를 점화식으로 나타낸다면 아래와 같다.

dp[i][c] = dp[i-1][c]

 

반면, 현재 허용하는 비용보다 앱을 비활성화하는데에 필요한 비용이 적은 경우, 현재 앱을 비활성화 할 수도 있고 안 할 수도 있다. 이 경우에는 비활성화 할 때와 비활성화 하지 않을 때 얻을 수 있는 메모리를 비교해서 더 큰 메모리 값을 얻을 수 있는 경우를 선택해야 한다.

 

비활성화 했을 때 얻을 수 있는 메모리는 아래와 같다.

dp[i][c] = i번째 앱이 차지하는 메모리 + dp[i-1][c - (i번째 앱을 비활성화 하는데에 필요한 비용)]

(여기서 i번째 앱을 비활성화 하는데에 필요한 비용을 빼주는 이유는, 최소한 i번째 앱이 차지하는 비용만큼은 필요하기 때문이다. 배낭 알고리즘으로 치자면 들어있는 물건을 빼야지만 현재 물건을 넣을 수 있는 경우도 있고 들어있는 물건을 빼지 않고도 현재 물건을 넣을 수 있는 경우가 있기 때문이다.)

 

비활성화 하지 않았을 때 얻을 수 있는 메모리는 아래와 같다.

dp[i][c] = dp[i-1][c]

 

즉, 위의 두 경우중에서 얻을 수 있는 메모리가 큰 값으로 dp[i][c]를 갱신하면 된다.

 

 

구현

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;    // N: 앱의 개수, M: 필요한 메모리

    static int[][] app;

    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        app = new int[N+1][2];

        st = new StringTokenizer(br.readLine());
        for (int n = 1; n < N+1; n++) {
            app[n][0] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int n = 1; n < N+1; n++) {
            app[n][1] = Integer.parseInt(st.nextToken());
        }

        dp = new int[N+1][10001];

        int answer = Integer.MAX_VALUE;

        for (int c = 0; c < 10001; c++) {
            for (int item = 1; item < N+1; item++) {
                int memory = app[item][0];
                int cost = app[item][1];

                // 현재 앱을 비활성화 할 수 없는 경우
                if (c < cost) {
                    dp[item][c] = dp[item-1][c];
                }
                // 현재 앱을 비활성화 할 수 있는 경우
                else {
                    if (memory + dp[item-1][c-cost] > dp[item-1][c]) {
                        dp[item][c] = memory + dp[item-1][c-cost];
                    }
                    else {
                        dp[item][c] = dp[item-1][c];
                    }
                }
                
                if (M <= dp[item][c]) {
                    answer = Math.min(answer, c);
                }
            }
        }

        System.out.println(answer);
    }
}