[BOJ] 7579. 앱

Knapsack을 활용한 문제이다.

Knapsack dp문제를 활용하여 접근해보았다. dp[N][cost]를 생성하고 메모리가 기준값을 넘을 때 마다 cost값을 최솟값으로 갱신하는 방법으로 접근해보았다. 맨처음 이 문제를 접근했을때 cost값대신 메모리 값으로 접근하였는데, cost 값기준으로 접근하는 것을 생각해내는데 오래걸렸다. 다만 cost값을 기준으로 접근하니깐 문제를 수훨하게 풀 수 있었다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_7579_앱 {
    static int N;
    static int standardCost;
    static int sumCost;
    static int answer;
 
    static int[] memory;
    static int[] cost;
    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 = Integer.parseInt(st.nextToken());
        standardCost = Integer.parseInt(st.nextToken());
 
        memory = new int[N + 1];
        cost = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            memory[i] = Integer.parseInt(st.nextToken());
        }
 
        sumCost = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
            sumCost += cost[i];
        }
 
        dp = new int[N + 1][sumCost + 1];
 
        answer = Integer.MAX_VALUE;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= sumCost; j++) {
                dp[i][j] = dp[i - 1][j];
 
                if (j - cost[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);
                }
 
                if (dp[i][j] >= standardCost) {
                    answer = Math.min(answer, j);
                }
            }
        }
 
        System.out.println(answer);
    }
}