BOJ_7579_앱_java

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

7579번: 앱

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

/**
 백준 7579번 앱
 골드 3
 */
public class BOJ_7579_앱 {
    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()); // 필요 메모리

        int A[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); // 사용 메모리
        int c[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); // 비활성화 비용

        int costSum = Arrays.stream(c).sum(); // cost 최대값

        App[] apps = new App[N+1];
        apps[0] = new App(0, -1, 0);
        for (int i = 1; i<=N; i++){
            apps[i] = new App(i, A[i-1], c[i-1]);
        }
        System.out.println(solution(N, M, apps, costSum));
    }

    public static int solution(int N, int M, App[] apps, int costSum){
        Arrays.sort(apps); // cost 오름차순 정렬
        int[][] dp = new int[N+1][costSum+1];
        int minCost = Integer.MAX_VALUE;
        for (int i = 1; i<N+1; i++){
           for (int j = 0; j<costSum+1; j++){
               if (j >= apps[i].cost) {
                   dp[i][j] = Math.max(dp[i-1][j-apps[i].cost] + apps[i].memory, dp[i-1][j]); // 해당 cost에서 가능한 최대 메모리 저장
               }else{
                   dp[i][j] = dp[i-1][j];
               }

               if (dp[i][j] >= M){ // M이상의 메모리를 차지하는 경우 최소값 찾기
                   minCost = Math.min(minCost, j);
               }
           }
        }

        return minCost;
    }

    public static class App implements Comparable<App>{
        int idx;
        int memory;
        int cost;
        public App(int idx, int memory, int cost){
            this.idx = idx;
            this.memory = memory;
            this.cost = cost;
        }

        @Override
        public int compareTo(App o) {
            return this.memory - o.memory;
        }

        @Override
        public String toString() {
            return "App{" +
                    "idx=" + idx +
                    ", memory=" + memory +
                    ", cost=" + cost +
                    '}';
        }
    }
}