생각 유도

우선적으로 보면 2^100 으로 안된다는 건 좀 알아야 한다. 왜 안된다는 걸 알면서도 시도를 했을 까. 여기서 브루트 포스는 걸러야 한다는 것을 알아야 하고.
처음에 배낭문제 비슷한 건가 생각을 했다. 그런데 m값이 너무 커서 해맸다.
생각의 전환으로 cost 를 인자값으로 넣고, 최대 비용을 찾은 다음에, 최대 비용 중 m 이 넘는 값 중에서 cost 가 가장 작은 값을 찾으면 된다.

dp[i][j] = i까지 봤는데 현재 j의 비용일 때 최대 메모리 수 .

방법

알게 된 것

1. 생각의 전환. m이 크다면 비용을 인자값으로 두자.
2. 나같은 경우에는 배낭 문제처럼 2차원 배열로 풀었지만, 1차원 배열로도 풀 수 있다.

   dp[i] = i 까지 봤을 때 최대 메모리 수.

생각해야 할 점

1. 브루트 포스 금지 - size부터 확인
2. 이거 보면 배낭 문제 바로 떠올라야 함.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P7579 {

    public static StringTokenizer st = null;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int n,m;

    public static int[] a;
    public static int[] c;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        a = new int[n + 1];
        for (int i =1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        c = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            c[i] = Integer.parseInt(st.nextToken());
        }

        // i까지 했을 때 현재 비용이 j
        long [][] dp = new long[n+1][10001];
        for (int i = 1 ; i<= n ; i++) {
            // dp[i][j] = dp[i-1][j-c[i]] + m[i];
            // 최대값
            for (int j = 0 ; j<= 10000 ; j++) {
                dp[i][j] = dp[i-1][j];
                if (j>= c[i]) dp[i][j] = Math.max(dp[i-1][j-c[i]] + a[i], dp[i][j]);
            }
        }
        for (int j = 0 ; j<= 10000 ; j++) {
            if (dp[n][j] >= m) {
                System.out.println(j);
                break;
            }
        }
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P7579 {

    public static StringTokenizer st = null;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int n,m;

    public static int[] a;
    public static int[] c;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        a = new int[n + 1];
        for (int i =1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        c = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            c[i] = Integer.parseInt(st.nextToken());
        }

        long [] dp = new long[10001]; // 비용이 i 일 때 최대 메모리 수
        // N번을 돌림 (모든 수 고려)
        for (int  i = 1; i<= n ; i++) {
            //c[i] <= 비용이 (j) <= 10000 는 되어야 함.
            for (int j  = 10000 ; j>=0 ; j--) {
                if (j>= c[i]) dp[j] = Math.max(dp[j],  dp[j-c[i]] +a[i]);
            }
        }
        for (int i = 0 ; i<= 10000 ; i++) {
            if (dp[i] >= m )
            {
                System.out.println(i);
                break;
            }
        }

    }
}

참고 자료

https://www.acmicpc.net/board/view/6667