문제

https://www.acmicpc.net/problem/7579

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

예제 입력 1
5 60
30 10 20 35 40
3 0 3 5 4
예제 출력 1
6

접근

배낭 문제다. 그런데 이제 약간의 변형을 곁들인....
일반적인 0/1 배낭 문제의 경우 가방 크기가 주어져 있고, 그 안에서 최대의 가치를 얻도록 물건을 담는 것이 목표이다.
반면 이 문제는 가치(=메모리)를 얻는 데 필요한 가방 크기(=비용)이 정해져 있지 않다. 따라서 가능한 모든 비용을 고려하면서 최적해를 찾아야 한다.

즉, 일반적인 0/1 배낭 문제와는 달리 2차원 배열에 메모이제이션을 해야 하는 것이다.
라고 당시에 써놨었는데, 최근 비슷한 문제를 풀며 1차원 배열로도 충분히 구현 가능하다는 걸 알았다. 배낭 문제 풀듯이 값을 뒤에서부터 역순으로 갱신해나가는 방식으로 메모이제이션을 하면 굳이 2차원 배열을 쓸 필요가 없다. 이건 나중에 다시 구현해봐야지...

사실 처음에는 메모리를 기준으로 메모이제이션을 해서 구현했다가 메모리 초과가 났다.
dp[i][j]에 첫 번째 앱에서부터 i번째 앱까지에서 j 바이트를 확보하기 위해 필요한 최소 비용을 저장하는 식으로.
처음엔 탑 다운으로 구현했어서 그런지 스택오버플로우가 나나? 해서 버텀업으로도 해봤는데 똑같았다.
원인은 이 dp 배열의 크기에 있었다. 가능한 M의 값의 범위가 0 이상 10000000 이하이기 때문에, dp 배열의 최대 크기가
N * M = 100 * 10000000 = 1000000000나 되기 때문이었다. int가 4byte를 차지하기 때문에 이 정도 배열 크기를 할당하려면 거의 4GB가 필요했다.

그래서 이 문제를 해결하려면 메모리가 아니라 비용을 기준으로 메모이제이션을 해야 했다.
dp[i][j]에 첫 번째 앱에서부터 i번째 앱까지에서 j만큼의 비용을 소모해 얻을 수 있는 최대 메모리를 저장하는 것이다.
dp 문제는 점화식만 잘 세우면 된다고 생각해서 메모리에 관해서는 크게 신경을 안 썼는데, 이럴 수도 있다는 걸 인지하게 되는 계기가 된 것 같다.

구현

1차 시도 (메모리 초과)

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] dp = new int[N + 1][M + 1];
        int[] A = new int[N + 1];
        int[] c = new int[N + 1];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], 1000000001);
            A[i] = Integer.parseInt(st1.nextToken());
            c[i] = Integer.parseInt(st2.nextToken());
        }

        for (int i = 1; i <= A[1]; i++) {
            dp[1][i] = c[1];
        }

        for (int range = 2; range <= N; range++) {
            for (int needed = 1; needed <= M; needed++) {
                if (needed <= A[range]) {
                    dp[range][needed] = Math.min(dp[range - 1][needed], c[range]); 
                } else {
                    dp[range][needed] = Math.min(dp[range - 1][needed], c[range] + dp[range - 1][needed - A[range]]); 
                }
            }
        }
    }
}

정답 풀이

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

class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        // dp[range][cost]: A_1부터 A_range까지의 앱 중에서 cost만큼의 비용을 소모해 얻을 수 있는 최대 메모리
        int[][] dp = new int[N + 1][10001]; 
        int[] A = new int[N + 1];
        int[] c = new int[N + 1];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st1.nextToken());
            c[i] = Integer.parseInt(st2.nextToken());
        }

        for (int i = c[1]; i <= 10000; i++) {
            dp[1][i] = A[1];
        }

        for (int range = 2; range < N; range++) {
            for (int cost = 0; cost < c[range]; cost++) {
                dp[range][cost] = dp[range - 1][cost];
            } 
            for (int cost = c[range]; cost <= 10000; cost++) {
                dp[range][cost] = Math.max(dp[range - 1][cost], A[range] + dp[range - 1][cost - c[range]]);
            }
        }
        for (int cost = 0; cost < c[N]; cost++) {
            if (dp[N - 1][cost] >= M) {
                System.out.println(cost);
                return;
            }
        }
        for (int cost = c[N]; cost <= 10000; cost++) {
            if (Math.max(dp[N - 1][cost], A[N] + dp[N - 1][cost - c[N]]) >= M) {
                System.out.println(cost);
                return;
            }
        }
    }
}

이런 문제는 보면 바로바로 해결할 수 있게 연습을 많이 해야겠다고 생각했다...!