백준 12920 평범한 배낭 2

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

이 문제는 어려워서 인터넷 보고 풀이 검색하고 풀이 해석한 다음에 다시 혼자 풀어봤다.

포인트1: n개까지 채울수 있다고 dp 배열을 어떤 물건을 1개 가지는 경우, 2개 가지는 경우, ... n개 가지는 경우를 다 따로 생각할 필요가 없음!! 왜냐면 이진법으로 모든 수를 나타낼 수 있기 때문에. 1, 2, 4, 8, ... 개 챙기는 경우만 고려.

포인트2: tot랑 flag 만든 이유. 이진법으로 한다고 1, 2, 4, 8, ... 로 하면 안됨. 배낭 최대 무게가 1~10000까지 아무 숫자로 주어지는데 2의 n승을 다 배열에 넣어버리면 합했을 때 배낭 최대 무게를 넘어버림!!

포인트3: dp 배열 채울 때 뒤에서부터 채우고 바깥 for문으로 물건 종류에 대해 갱신하는 거를 반복해야 제대로 채울 수 있음.

 

#include <iostream>
using namespace std;
int val[10002]; // 무게
int happy[10002]; // 만족도
int MaxVal[10002]; // dp배열
int n,m;
int main()
{
    int ct=0;
    cin >> n >> m;
    for(int i=0;i<n;++i)
    {
        int v,c,k;
        cin >> v >> c>> k;
        int tot=0;
        int flag=1;
        for(int i=1;tot<k&&flag;i*=2)
        {
            tot+=i;
            if(tot>=k)
            {
                tot-=i;
                i=k-tot;
                flag=0;
            }
            val[ct]=v*i;
            happy[ct]=c*i;
            ct++;
        }
    }
    for(int i=0;i<ct;++i)
    {
        for(int j=m;j>=val[i];j--)
            MaxVal[j]=max(MaxVal[j],MaxVal[j-val[i]]+happy[i]);
    }
    cout << MaxVal[m];
}