[BOJ] 7579:앱

0. 문제

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

7579번: 앱

 

1. 문제분석

- 기존의 상태(기존에 종료 또는 종료하지 않은 앱으로 인해 획득한 메모리)에 대해서 기존의 상태를 바꿀 수 있는 경우의 수(기존에 종료한 앱 이외에 새로운 앱을 종료하는 것) 중, 그 최댓값(얻을 수 있는 메모리)을 찾아 조건을 만족하는(주어진 목표 메모리 m보다 크거나 같은) dp 값을 찾아 해당 dp의 2차원 인덱스인 비용의 최솟값을 찾는다는 점에서 Knapsack 알고리즘과 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다.

- dp[n][c] : n번째 앱까지 종료하거나 하지 않았을 때,  c 이하의 비용을 사용해 얻을 수 있는 최대의 메모리

2. 주의할 점

- 최소의 비용을 찾는 관점에서 dp를 사용해 문제를 풀게 되면, 메모리가 부족해진다. 따라서 사용 가능한 최대의 메모리를 찾고, 주어진 목표 메모리 이상의 값을 갖는 dp 배열의 cost 인덱스를 찾아야 한다.

- knapsack 알고리즘 자체만으로는 최소 리밋을 만족하는, 최소의 값을 찾을 수 없다. 최대 리밋을 만족하는 최대의 값을 찾고, 이를 만족하는 값들 중 최솟값을 찾는 방식으로 knapsack 알고리즘을 이용해야 한다.

- 전형적인 knapsack 알고리즘 문제의 변형(knapsack=종료시킬 앱의 집합, knapsack에 넣을 물건=종료시킬 앱)이므로, 기존에 알고 있던 knapsack 알고리즘의 유의사항을 잘 생각하며 접근해야 한다.

• 단순히 무게만 생각하다보면 무게 조건만 만족하는 코드(각 물건은 한 개씩만 가방에 들어갈 수 있다는 조건을 무시하게 된다든지)를 짜게된다. 하지만 문제의 조건은 "각 물건은 하나씩만 존재하고, 반복해서 넣을 수 없음"임을 명심하자.
• 조건을 잘 읽어야 한다. 최대 K 무게까지의 배낭을 들 수 있다고 했으므로, 단순히 배낭에 넣은 물건 무게의 합이 정확하게 K 무게일 경우가 아니라 무게의 최댓값이 K인 경우, 즉 실제 무게는 K 이하인 경우를 모두 고려해서 dp 값을 구해야 한다. 
• 어떤 물건을 몇 번째로 넣느냐는 전혀 상관없다. 따라서 물건을 어떤 순서로 넣든 간에 순차적으로 N개의 모든 물건에 대한 경우의 수를 한번씩 고려해야 한다.

3. 소스코드(Java)

3-1. 메모리 초과 소스코드

// boj 7579 앱
// knapsack
// dp

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

public class boj_07579 {
    static int n, m;

    // b(yte)[i] : i번째 앱을 껐을 때 얻는 메모리 바이트 수
    // c(ost)[i] : i번째 앱을 껐을 때 발생하는 비용
    static int[] b, c;

    // dp[i][j][0] : i번째 앱을 끄거나 끄지 않을 때, j 바이트 만큼의 메모리를 획득할 수 있는 최소 비용
    // dp[i][j][1] : i번째 앱을 끄거나 끄지 않을 때, 최소 j 바이트 만큼의 메모리를 획득할 수 있는 총 메모리
    static int[][][] dp;

    // 최대로 발생할 수 있는 총 비용 (n <= 100, c[i] <= 100)
    static final int MAX = 100 * 100 + 1;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        b = new int[n];
        c = new int[n];
        dp = new int[n][m+1][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i <n; ++i) b[i] = stoi(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i <n; ++i) c[i] = stoi(st.nextToken());
        for (int i = 0; i <n; ++i) {
            for (int j = 0; j <= m; ++j) dp[i][j][0] = MAX;
        }
        for (int mem = 0; mem <= m; ++mem) {
            if (b[0] >= mem) {
                dp[0][mem][0] = c[0];
                dp[0][mem][1] = b[0];
            }
        }
        for (int app = 1; app < n; ++app) {
            for (int mem = b[app]; mem <= m; ++mem) {
                if (dp[app-1][mem - b[app]][1] + b[app] >= mem) {
                    dp[app][mem][0] = Math.min(
                            dp[app-1][mem-b[app]][0] + c[app], dp[app-1][mem][0]);
                    dp[app][mem][1] = dp[app-1][mem - b[app]][1] + b[app];
                } else dp[app][mem] = dp[app - 1][mem];
            }
        }
        System.out.print(dp[n-1][m][0]);
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

 

3-2. 통과코드

// boj 7579 앱
// knapsack
// dp

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

public class boj_07579 {
    // 최대로 발생할 수 있는 총 비용 (n <= 100, c[i] <= 100)
    static final int MAX = 100 * 100 + 1;

    static int n, m;

    // b(yte)[i] : i번째 앱을 껐을 때 얻는 메모리 바이트 수
    // c(ost)[i] : i번째 앱을 껐을 때 발생하는 비용
    static int[] b, c;

    // dp[i][j] : i번째 앱까지 종료하거나 켰을 때, 비용이 j 이하일 경우에 얻을 수 있는 최대 메모리
    static int[][] dp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        b = new int[n];
        c = new int[n];
        dp = new int[n][MAX + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) b[i] = stoi(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) c[i] = stoi(st.nextToken());
        for (int cost = c[0]; cost <= MAX; ++cost) dp[0][cost] = b[0];
        for (int app = 1; app < n; ++app) {
            for (int cost = 0; cost <= MAX; ++cost) {
                if (cost >= c[app]) dp[app][cost] = Math.max(
                     dp[app-1][cost], dp[app-1][cost - c[app]] + b[app]);
                else dp[app][cost] = dp[app-1][cost];
            }
        }
        for (int cost = 0; cost <= MAX; ++cost)
            if (dp[n -1][cost] >= m) {
                System.out.print(cost);
                break;
            }
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

4. 여담

- 구하려는 것을 dp 배열의 값으로 놓는 것이 아니라, index로 넣는 발상의 전환이 필요한 문제였다...!

- 같은 knapsack 알고리즘을 적용하는 boj 12856 문제의 알고리즘 가져다 썼다