아이디어

• "비용"이 weight(cost), "메모리"가 value가 되는 가방 문제
  • 2차원 배열 memo[i][j]를 사용한다.
  • memo[i][j]: 앱 $A_1$~$A_i$을 고려했을 때 비용 합이 j인 경우 메모리 합
• memo[N][i]가 M일 때 i의 최솟값을 구하면 정답

코드

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

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tk = null;

    static int N, M, ans;
    static int[] m, c;

    // memo[i][j]: A_1~A_i까지만 고려하고 비용 합이 c[i]가 되는 경우
    static int[][] memo;
    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());

        m = new int[N+1];
        tk = new StringTokenizer(rd.readLine());
        for (int i = 1; i <= N; i++) {
            m[i] = Integer.parseInt(tk.nextToken());
        }

        c = new int[N+1];
        tk = new StringTokenizer(rd.readLine());
        for (int i = 1; i <= N; i++) {
            c[i] = Integer.parseInt(tk.nextToken());
        }

        memo = new int[N+1][10001];

        // ...
        for (int i=1; i<=N; i++) {
            for (int j = 0; j <= 10000; j++) {
                if (j >= c[i])
                    memo[i][j] = Math.max(memo[i-1][j], memo[i-1][j-c[i]] + m[i]);
                else 
                    memo[i][j] = memo[i-1][j];
            }
        }

        for (int i = 10000; i >= 0; i--) {
            if (memo[N][i] >= M)
                ans = i;
        }

        System.out.println(ans);
    }
}

메모리 및 시간

• 메모리: 18448 KB
• 시간: 156 ms

리뷰

• 처음 볼때는 난감했는데 평범한 가방 문제였다.
• 주의: 비용 합이 0인 경우도 정답이 될 수 있다.
  • for문 범위와 인덱스 주의