[c++] 백준 #12920 평범한 배낭 (190903)

< 풀이 >

보자마자 knapsack 문제가 생각났다. 단순 DP 문제처럼 접근하려 했지만.. But..

단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다.

라는 조건 때문에 평범한 방법으로는 풀 수가 없다.(진짜로 n개씩 다 집어넣어보고 하면 시간초과가 날 것이다.)

n이 100만, w는 1만이라서 애초에 dp[n][w]로 배열 선언도 못한다.

그래서, 좋은 아이디어는 1, 2, 4, 8, 16, 32, 64, 128, 256, 1000-511 이런 식으로 해서 묶음을 1000개에서 9개로 바꾸는 것이다. 10000개의 묶음이면 15~16개 정도가 되는 것이고, 많아봤자 물건이 1600개니까.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

vector<ii> items;
vector<vector<int> > DP(2010,vector<int>(10010, -1));

int knapsack(int N, int W){
    // base case
    if (N==0 || W==0) return 0;
    
    int& ret = DP[N][W];
    if (ret != -1) return ret;

    int& wt = items[N-1].first;
    int& val = items[N-1].second;

    if (wt > W) return ret = knapsack(N-1, W); // 아예 못넣는 경우
    else return ret = max(val + knapsack(N-1, W-wt), knapsack(N-1, W)); 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int N, M;
    cin >> N >> M;
    for(int i=0; i<N;i++){
        int V, C, K;
        cin >> V >> C >> K;
        int j=1;
        for(; ((j*2)-1)<=K;j*=2){ // 1, 2, 4, 8, 16, 32, 64, 128, 256
            items.push_back({V*j, C*j});
        }
        int remain = (K-(j-1));
        items.push_back({V*remain, C*remain}); // 1000-511 = 489
    }

    int n = items.size();

    // knapsack DP!
    cout << knapsack(n, M) << '\n';
    return 0;
}