BOJ 7579번 앱 ( DP, 배낭 문제 ) JAVA

BOJ 7579번 앱 ( DP, 배낭 문제 ) JAVA

---

풀이

처음부터 배낭 문제라고 떠오르기 쉽지 않았다. 

그 이유는 일단 M의 범위가 너무나 컸는데, DP로 해결을 하려 해도 시간초과가 걸릴 것이라 예상되었기 때문이다.

 

하지만, 메모리가 아닌 비용을 기준으로 문제를 다르게 생각해보면 배낭 문제로 접근 가능함을 알 수 있다.

배낭 문제를 응용한 문제라 정의하면 될 것 같다.

 

결국은 알고리즘 해결은 여러 가지 알고리즘을 일단 자기 것으로 만드는 게 첫 번째.

그리고 그 무기들을 적재적소에 잘 활용하는 게 두 번째라는 것을 다시 한 번 느낄 수 있었다.

 

링크

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

 

소스 코드

---

package boj;

import java.util.Scanner;

public class Boj7579 {
    static int n, m;
    static long[] mem;
    static int[] cost;
    static int ans = 20000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        mem = new long[n + 1];
        cost = new int[n + 1];
        int col = 0;
        for (int i = 1; i <= n; i++) {
            mem[i] = sc.nextLong();
        }
        for (int i = 1; i <= n; i++) {
            cost[i] = sc.nextInt();
            col += cost[i];
        }
        long[][] dp = new long[n + 1][col + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= col; j++) {
                if (j - cost[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i]] + mem[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
                if (dp[i][j] >= m) {
                    ans = Math.min(ans, j);
                }
            }
        }
        System.out.println(ans);
    }

}