<DP> BOJ 7579 앱

문제

실행중인 앱 중에서 재실행할 비용과 현재 점유중인 메모리가 주어지고 새로운 앱을 실행하기 위해 앱을 종료시킬 최소 비용을 구하는 문제입니다.

• 실행중인 앱의 개수 N <= 100
• 실행할 앱의 메모리 M <= 10000000
• 실행중인 앱을 재실행하기 위한 비용 c <= 100
• 실행중인 앱의 메모리 m의 합 <= 10000000

접근

문제를 읽어보면 knapsack문제와 유사한 구조라는 걸 알 수 있습니다.
그러면 knapsack 문제를 생각해봅니다. 각 물건에 대한 가치와 무게가 주어지고 제한된 무게를 담을 수 있는 가방에 넣을 수 있는 최대가치를 구합니다.
각 변수를 현재 문제와 연결해봅니다

• 가치 => 실행중인 앱을 종료하여 얻는 메모리
• 무게 => 실행중인 앱을 종료 후 재실할 때 필요한 비용

즉 제한된 비용에 대해 최대 가치를 얻는 문제로 바꿔 생각할 수 있습니다.
이런 방법으로 문제를 해결하기 위해서 우리는 2차원 배열이 필요하며 그 배열의 크기는 100x100x100입니다. 100만이죠. 또한 하나의 배열을 구하기 위한 호출 횟수는 2회이므로 200만의 복잡도로 문제가 해결가능합니다. 주의 사항으로 답을 구하기 위해서는 0부터 최대 비용 까지 for문을 돌며 해당하는 최대 가치가 M을 넘으면 for문을 종료하고 답을 출력해주면 됩니다.

knapsack문제와 유사하지만 최대가치를 구하는 것이 아니라 원하는 가치에 대한 최소비용을 구하는 문제라 접근이 조금은 어려울 수 있었던 문제라고 생각합니다.

knapsack 문제의 정석 풀이

코드

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

class Pair {
    int m;
    int c;

    Pair(int m, int c) {
        this.m = m;
        this.c = c;
    }
}

class baek__7579 {
    static Pair[] pairs = new Pair[101];
    static int[][] d = new int[100 * 100 + 1][101];

    static int go(int c, int n) {
        if (c <= 0) {
            if (c == 0)
                return 0;
            return -20000000;
        }
        if (n < 0)
            return 0;

        if (d[c][n] != -1)
            return d[c][n];

        d[c][n] = Math.max(go(c - pairs[n].c, n - 1) + pairs[n].m, go(c, n - 1));

        return d[c][n];
    }

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

        String[] temp = br.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        temp = br.readLine().split(" ");
        String[] temp1 = br.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            int memory = Integer.parseInt(temp[i]);
            int cost = Integer.parseInt(temp1[i]);
            pairs[i] = new Pair(memory, cost);
        }

        for (int i = 0; i < 100 * 100 + 1; i++) {
            for (int j = 0; j < 101; j++) {
                d[i][j] = -1;
            }
        }

        for (int i = 0; i < 100 * 100 + 1; i++) {
            if (go(i, n - 1) >= m) {
                System.out.print(i);
                return;
            }
        }
    }
}