[ BOJ ][JAVA][1480] 보석모으기

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

1480번: 보석 모으기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	665	213	159	33.403%

문제

세준이는 잘 모르겠지만, 세준이는 보석에 미쳐있다. 따라서, 숌 보석상에 있는 모든 보석을 다 훔치려고 한다. 하지만, 세준이는 보석을 다 가져올 수는 없다. 그 이유는 가방의 개수에 제한이 있고, 한 가방마다 넣을 수 있는 보석의 개수가 제한이 있기 때문이다. 세준이는 M개의 가방을 가지고 있다. 그리고 각각의 가방은 C그램의 보석을 담을 수 있다.

숌 보석상에는 보석이 N개 있다. N개의 보석의 무게가 주어졌을 때, 세준이가 훔칠 수 있는 보석의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보다 크고, 20보다 작거나 같은 자연수이다. 둘째 줄에 보석의 무게가 하나씩 주어진다. 보석의 무게는 1보다 크거나 같고, 20보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 가져갈 수 있는 최대 보석의 개수를 출력한다.

예제 입력 1

5 2 5
2 2 2 2 2

예제 출력 1

4

코드

/*
    1480
    보석모으기
    knapsack + bitmasking

    n : 보석의 개수
    m : 가방의 개수
    c : 가방의 최대 한도
    dp[n][m][c]
*/
import java.io.*;
import java.util.*;
public class p1480 {
    static final int MAX = 14;
    static int n, m, c;
    static int[] arr;
    static int[][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        arr = new int[n];
        dp = new int[1 << MAX][11][21];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 0(bit)을 시작으로, 0번째(idx) 가방부터 탐색, 처음 허용용량은 c
        int answer = recur(0, 0, c);
        System.out.println(answer);
    }
    static int recur(int path, int idx, int k) {
        // 모든 보석이나, 모든 가방을 사용했다면 return
        if ((path == (1 << n) - 1) || idx == m) {
            return 0;
        }

        // 이미 방문한 곳이라면
        if (dp[path][idx][k] != 0) {
            return dp[path][idx][k];
        }

        for (int i = 0; i < n; i++) {
            // path의 i번째 보석이 사용되었거나(bit on), 남은 용량이 해당 보석의 무게보다 작다면 넘어감
            if ((path & (1 << i)) > 0) {
                continue;
            }

            // 해당 가방(idx)의 용량이 남아있다면, 다음 보석을 담기 위해 그 가방을 계속 사용
            if (k >= arr[i]) {
                dp[path][idx][k] = Math.max(dp[path][idx][k], recur(path | (1 << i), idx, k - arr[i]) + 1);    
            } else {
                // 다음 가방(idx + 1)을 탐색
                dp[path][idx][k] = Math.max(dp[path][idx][k], recur(path, idx + 1, c));
            }

        }

        return dp[path][idx][k];
    }
}