백준 1480번: 보석 모으기 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

보석 모으기

풀이

$i$번째 보석의 무게를 $w_i$라 합시다.

첫번째 가방부터 $M$번째 가방까지 순서대로 보석을 담읍시다. 이때 가방은 더 이상 어떤 보석도 담을 수 없는 가방과 더 보석을 담을 수 있는 가방으로 나누어 볼 수 있습니다. 더 보석을 담을 수 있는 가방을 하나 골라 더 담을 수 없을 때 까지 보석을 담고 다음 가방에 보석을 채운다고 생각해 봅시다.

보석을 더 담을 수 있는 가방이 $b$개 남았고, 현재 가방에 $c$만큼의 용량이 남았고, 이때까지 훔친 보석의 집합은 $j$일 때 더 훔칠 수 있는 보석의 최댓값을 $DP[b][c][j]$라 합시다. 아직 훔치지 않은 임의의 보석의 번호 $i$에 대해 아래 점화식이 성립합니다.

\[DP[b][c][j] = \max(DP[b][c - w_i][j\ |\ 2^i] + 1, DP[b-1][C][j])\]

답은 $DP[M][C][0]$입니다. 동적 계획법을 사용하면 시간 복잡도 $\mathcal{O}(MC2^N)$에 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int N, M, C;

int weight[25];
int dp[20][25][1 << 15];

int getDP(int bag, int c, int jewel) {
    if (bag == 0)
        return 0;

    int& ret = dp[bag][c][jewel];
    if (ret != -1)
        return ret;

    ret = 0;
    for (int i = 0; i < N; i++) {
        if (jewel & (1 << i))
            continue;
        if (c - weight[i] < 0)
            continue;

        ret = max(ret, 1 + getDP(bag, c - weight[i], jewel | (1 << i)));
    }

    ret = max(ret, getDP(bag - 1, C, jewel));
    return ret;
}

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

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

    for (int i = 0; i < N; i++)
        cin >> weight[i];

    cout << getDP(M, C, 0);

    return 0;
}

백준 1480번: 보석 모으기 [C++]