[BOJ 12920] 평범한 배낭 2

[문제] : https://www.acmicpc.net/problem/12920

12920번: 평범한 배낭 2

 

[필요 개념]

- DP , 배낭 문제 (Knap-sack)

- 비트마스크

 

[풀이]

전형적인 배낭문제 (Knapsack)처럼 보이나, 이 문제에서는 특별하게 고려해줘야 하는 부분이 있다. 

바로 같은 종류의 물건의 개수가 2개 이상일 수 있다는 것이다. 

원래 배낭문제에서는 각 물건이 하나씩 있어, 해당 물건을 넣거나 빼는 두가지 경우만 있었는데, 이 문제같은 경우에는 물건의 개수가 여러개가 있어서 경우가 훨씬 많아졌다. 

처음에는 같은 종류의 물건들을 모두 다르게 생각해서, dp에 추가해주는 방식을 이용해볼 수 있다.

int dp[10001];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M; cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int v, c, k; cin >> v >> c >> k;

        while (k--) {
            for (int j = M; j >= v; j--) {
                dp[j] = max(dp[j - v] + c, dp[j]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= M; i++) ans = max(dp[i], ans);
    cout << ans;
}

 

위의 코드는 k개의 같은 종류의 물건들을 하나씩 dp에 저장해주는 과정이다.

이 방식을 이용하게 되면 물론 시간초과가 발생하게 된다. 물건 한 종류당 최대 10000개가 존재할 수 있으므로, V = 1, M = 10000, K = 10000이 되면 while문이 1억번 돌게 된다. 

그렇다면 어떻게 해야할까? 핵심 아이디어는 2진수 비트(bit)를 이용하는 것이다. 

예를 들어서 한 물건을 7개 담은 경우를 생각해보자. 위의 방식대로라면 물건을 하나씩 추가하면서 dp를 갱신하므로 총 7번 반복하게 된다. 

하지만, 7은 1 + 2 + 4 이므로, 1개를 더 추가한 경우와, 2개를 더 추가한 경우, 4개를 더 추가한 경우 모두 dp에 갱신을 시키면 결국 7개가 추가된 경우가 자동으로 갱신이 된다. 

이런 방식으로 물건을 1개씩 추가하는 것이 아니라, 2의 거듭제곱씩 추가하게 되면 모든 수를 다 고려할 수 있게 된다. 

모든 자연수는 2의 거듭제곱의 합으로 나타낼 수 있기 때문이다. (이진수로 바꿨을 때, 1인 자리들만 덧셈)

따라서 아래와 같이 코드 작성이 가능하다.

 

소스코드)

int dp[10001];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M; cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int v, c, k; cin >> v >> c >> k;
        int t = 1;
        int temp;
        while (k > 0) {
            temp = min(k, t);
            for (int j = M; j >= v*temp; j--) {
                dp[j] = max(dp[j - v*temp] + c*temp, dp[j]);
            }
            t *= 2;
            k -= temp;
        }
    }
    int ans = 0;
    for (int i = 0; i <= M; i++) ans = max(dp[i], ans);
    cout << ans;
}