백준 1480 - 보석 모으기

icpc.me/1480

 

솔루션 - 이차원 DP

테이블을 다음과 같이 정의한다.

 

dp[i][j] := i번째 가방까지 보석의 조합을 비트마스크로 표현한 j로 채우는게 가능한가?

 

첫번째 가방에 보석을 채울 수 있는 경우를 비트마스크로 확인하고 다음 가방에 다른 보석을 넣는 경우를 계산한 후 m번째 가방까지 썼을 때 최대 비트를 구해 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
bool dp[11][1 << 13];
int jewel[13];
 
int n, m, c;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n >> m >> c;
 
    for (int i = 0; i < n; ++i)
        cin >> jewel[i];
    sort(jewel, jewel + n);
 
    int x = (1 << n) - 1;
 
    while (x)
    {
        int tmp = 0;
        for (int i = 0; i < n; ++i)
            if ((1 << i) & x)
                tmp += jewel[i];
        
        if (tmp <= c)
            dp[1][x] = true;
 
        --x;
    }
 
    for (int i = 1; i <= m - 1; ++i)
    {
        for (int j = 0; j < (1 << n); ++j)
        {
            if (!dp[i][j])
                continue;
            
            dp[i + 1][j] = true;
 
            int b = (1 << n) - 1;
 
            while (b)
            {
                if ((b & j) != j || b == j)
                {
                    --b;
                    continue;
                }
                
                int remain = b & ~j;
                int tmp = 0;
 
                for (int k = 0; k < n; ++k)
                    if ((1 << k) & remain)
                        tmp += jewel[k];
 
                if (tmp <= c)
                    dp[i + 1][b] = true;
                
                --b;
            }
        }
    }
 
    int ret = 0;
 
    for (int i = (1 << n) - 1; i >= 0; --i)
        if (dp[m][i])
            ret = max(ret, __builtin_popcount(i));
    
    cout << ret;
}

솔루션 - 삼차원 DP

테이블을 다음과 같이 정의한다.

 

dp[i][j][k] := i번째 가방까지 보석의 조합을 비트마스크 j만큼 쓰고 i번째 가방의 용량이 k 남았을 때 최대 갯수

 

탑다운 dp를 수행하여 모든 가방을 썼을 때 비트 개수의 최대값을 구하면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int dp[11][1 << 13][21];
int jewel[13];
 
int n, m, c;
 
int memo(int idx, int bt, int cap);
 
int main()
{
    memset(dp, -1, sizeof dp);
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n >> m >> c;
 
    for (int i = 0; i < n; ++i)
        cin >> jewel[i];
    
    cout << memo(0, 0, 0);
}
 
int memo(int idx, int bt, int cap)
{
    if (idx == m)
        return __builtin_popcount(bt);
 
    int &ret = dp[idx][bt][cap];
 
    if (ret != -1)
        return ret;
    
    ret = 0;
 
    for (int i = 0; i < n; ++i)
    {
        if ((1 << i) & bt)
            continue;
        
        int nxtbit = bt | (1 << i);
        
        if (cap + jewel[i] <= c)
            ret = max(ret, memo(idx, nxtbit, cap + jewel[i]));
    }
 
    ret = max(ret, memo(idx + 1, bt, 0));
 
    return ret;
}

테이블의 차원을 낮게 잡아도 실행 시간이 무조건 더 빠르지는 않음을 알 수 있는 문제였다.