백준 7579 앱

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

N은 100이라 완탐이 불가하다
필요한 메모리를 제거하기 위해
최소 비용을 구하는 문제다
M의 범위가 1천만이라 DP 테이블을 만들지 못한다.
DP테이블을 메모리를 저장하는 DP[100(프로세스 수) * 100(비용)] 짜리 테이블을 만들어서
최대 비용인 cost.sum()을 통해 뒤에서 부터 값을 갱신했다.

마지막에 DP를 순회하면서 
DP[i]가 M 메모리 이상 확보되었다면 i를 출력해주면 된다.

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

public class Main {
    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 memory[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer:: parseInt).toArray();
        int cost[]= Arrays.stream(br.readLine().split(" ")).mapToInt(Integer:: parseInt).toArray();
        int cR = Arrays.stream(cost).sum();


        long DP[] = new long[10101];


        for(int i = 0; i < N; i++) {
            for(int j = cR; j >= 1; j--) {
                // 60 바이트를 확보하기 위해
                if(j >= cost[i]) {
                    DP[j] = Math.max(DP[j], DP[j - cost[i]] + memory[i]);

                }
            }
        }
        int result = 0;
        for(int i = 0; i <= cR; i++) {
            if(DP[i] >= M) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }

}