문제 - 7579

문제접근

배낭문제와 비슷한 문제로 dp로 해결을 하면 된다.
하지만 배낭처럼 dp[i][j]를 할 경우 j를 무게로 잡는 즉 메모리를 잡으면 메모리초과가 난다. 100 * 10_000_000으로 int로는 할 수가 없다.
그래서 j를 총 비용으로 설정을 해야된다.

dp[i][j] : i번째 앱까지 사용할때 비용 j로 확보할 수 있는 메모리의 크기를 나타낸다.
ex)
dp[0][1] = 0 : 0번째 앱으로 비용 1로 만들 수 있는 메모리의 크기는 0이다.
dp[0][3] = 30

으로 점화식은
dp[i][j] = max(memory + dp[i-1][j-cost],dp[i-1])
으로 설정을 하고
첫번째 앱을 비활성화시에는 아무런 값이 없기 때문에 초기값을 설정해준다.

소스코드

import java.util.*;
import java.io.*;
public class bj_7579 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int max_value = 10_001;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int [][]dp = new int[N][max_value];
        int ans = Integer.MAX_VALUE;

        st = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int []costs = new int[N];
        int []capacitys = new int[N];

        for(int i=0;i<N;i++)
        {
            int capacity = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st2.nextToken());
            costs[i] = cost;
            capacitys[i] = capacity;
        }

        //i번째까지의 앱을 사용할 경우
        for(int i=0;i<N;i++)
        {

            int cnt_cost = costs[i];
            int cnt_capacity = capacitys[i];
            //총 비용
            for(int j=0;j < max_value;j++)
            {
                //앱이 하나일 경우는 현재 메모리 저장
                if(i==0)
                {
                   if(j >= cnt_cost) dp[i][j] = cnt_capacity;
                }else{
                    if(j >= cnt_cost)
                    {
                        dp[i][j] = Math.max(cnt_capacity + dp[i-1][j-cnt_cost],dp[i-1][j]);
                    }else{
                        dp[i][j] = dp[i-1][j];
                    }
                }

                if(dp[i][j] >= M) ans = Math.min(ans,j);
            }
        }

        System.out.println(ans);


    }

}