[백준] 7579번 - 앱 [Java]

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

 

[백준] 7579번 - 앱 [Java]

[백준] 7579번 - 앱 [Java]

---

1.  아이디어

 

0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.
앱을 비활성화하는 비용을 무게, 앱을 비활성화해서 확보할 수 있는 메모리를 가치로 생각하면 된다.

---

2. 문제풀이

 

1차원 dp, 2차원 dp 두 가지 방식으로 모두 풀어봤고 dp 테이블에는 확보할 수 있는 메모리를, 인덱스에는 비활성화하는데 필요한 비용을 두면 된다. 비활성화하는데 필요한 비용이 0일 수 있어서 인덱스 0부터 모두 사용하고 이후 정답을 찾을 때도 0번 인덱스부터 탐색을 해야한다. 정답은 최소 비용으로 M 이상의 메모리를 확보해야하는데 인덱스 자체가 이미 정렬이 된 개념이어서 앞에서부터 순회하면 된다.

---

3. 코드

 

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

public class Main_1D {

    private static class Item {
        int m;
        int c;
    }

    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());

        Item[] items = new Item[1 + N];
        for (int i = 1; i <= N; i++) {
            items[i] = new Item();
        }

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

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

        int[] dp = new int[1 + max];

        for (int i = 1; i <= N; i++) {
            for (int j = max; j >= items[i].c; j--) {
                dp[j] = Math.max(dp[j], dp[j - items[i].c] + items[i].m);
            }
        }

        for (int i = 0; i <= max; i++) {
            if (dp[i] >= M) {
                System.out.println(i);
                return;
            }
        }
    }
}

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

public class Main_2D {

    private static class Item {
        int m;
        int c;
    }

    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());

        Item[] items = new Item[1 + N];
        for (int i = 1; i <= N; i++) {
            items[i] = new Item();
        }

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

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

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

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= max; j++) {
                if (j < items[i].c) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i].c] + items[i].m);
            }
        }

        for (int i = 0; i <= max; i++) {
            if (dp[N][i] >= M) {
                System.out.println(i);
                return;
            }
        }
    }
}

---

4. 후기

 

- 1차원 dp

- 2차원 dp