[백준 c++] 1480 보석 모으기

문제

https://www.acmicpc.net/problem/1480
보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C일 때,
가져갈 수 있는 최대 보석의 개수를 출력하는 문제다.

---

풀이

dp를 이용한 풀이
dp[가방 index][지금까지 넣은 보석들][남은 용량]

1. 지금까지 넣은 보석들의 목록

가방끼리 겹치지 않게 담으려면 지금까지 넣은 보석들의 목록을 가져와야했다.

이걸 배열로 또 담을수도 없고 어쩌지 했는데 비트마스크를 이용해서 풀면 된다.

비트마스크 : 정수의 이진수 표현을 자료 구조로 쓰는 기법

보석개수가 총 5개일 때 0번 보석, 3번 보석을 넣었다면 01001 이런식으로 표현되는 것이다.

2. dfs

이 문제는 주의해야할 것이 있는데
전에 풀었던 가방에 보석 넣는 문제는 가방이 한 개였다.
그런데 이 문제는 가방이 여러 개라서 dfs를 2번 돌려야한다.

1. 다음 가방에 담기
2. 지금 가방에 이어서 담기

2개 가방에 4개의 보석을 담을 수 있는 경우들을 간단하게 그래프로 그려보자.
(아무것도 안넣은 경우의 수를 까먹고 안그림; [0,0,0,0]도 생각해야한다.)
1) 1번 가방에 dfs를 이용해서 보석을 담는다. (차례대로 1번보석 넣음, 2번보석 넣음, 3번 보석 넣음, 4번 보석 넣음)
2) 1번 보석 넣은 상태에서 또 dfs를 돌려서 보석을 넣을 수가 있겠다.

⭐️ 3) 1번 가방에 한 번 넣은 상태에서 가방 index+1로 dfs돌려야한다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, c, a[14], dp[11][1 << 13][21];

int go(int bagNum, int yam, int capacity)
{
    if (bagNum == m)
        return 0;
    int &ret = dp[bagNum][yam][capacity];
    if (ret)
        return ret;
    ret = max(ret, go(bagNum + 1, yam, c));
    for (int i = 0; i < n; i++)
    {
        bool beforeYam = (1 << i) & yam;
        bool canYam = (capacity - a[i]) >= 0;
        if (canYam && !beforeYam)
            ret = max(ret, go(bagNum, yam | (1 << i), capacity - a[i]) + 1);
    }
    return ret;
}
int main()
{
    cin >> n >> m >> c;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << go(0, 0, c) << "\n";
}