[백준] 12920번 평범한 배낭 2 C++

문제 출처: https://www.acmicpc.net/problem/12920

12920번: 평범한 배낭 2

평범한 배낭 문제처럼 접근하여 푼다면 각 아이템마다 0~10000번씩 호출을 하게 되어서

10000^100의 시간 복잡도를 가지게 된다.

각 아이템을 1개씩 구매하는 것이 아니라 이진법 표기처럼 아이템 15개를 1개 2개 4개 8개로 묶어서 판매한다면 0~15개를 모두 살 수 있다. 아이템 14개 또한 1개 2개 4개 7개로 묶어서 판매한다면 0~14개를 모두 표현 가능하다.

이렇게 묶게 되면 최대 10000개의 물건 개수를 log 10000 으로 줄일 수 있게 된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

int itemCount = 0;
int N, M;
int weight[3000], happy[3000];
int dp[3000][10001];

int backpack(int now, int nowWei) {
    if (now == itemCount)return 0;
    if (dp[now][nowWei] != -1)return dp[now][nowWei];

    int val = backpack(now + 1, nowWei);
    if (nowWei - weight[now] >= 0)
        val = max(val, backpack(now + 1, nowWei - weight[now]) + happy[now]);

    dp[now][nowWei] = val;
    return val;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    fill(&dp[0][0], &dp[2999][10001] , -1);
    cin >> N >> M;

    
    for (int i = 0; i < N; i++) {
        int w, h, c;
        cin >> w >> h>> c;
        int k = 1;
        while (c > 0) {
            if (c > k) {
                c = c - k;
                weight[itemCount] = k * w;
                happy[itemCount] = k * h;
                itemCount++;
                k = k * 2;
            }
            else {
                
                weight[itemCount] = c * w;
                happy[itemCount] = c * h;
                itemCount++;
                c = c - c;
            }
        }
    }
    

    int val = backpack(0, M);
    cout << val;

}