비트마스크(& 연산자)를 이용하여, 시간 복잡도 줄이기 in C++

사람마다 좋아하는 숫자 m개가 있고, 1부터 d까지의 정수형 숫자 배열중 1부터 k개를 선택했을때, k개의 숫자가 사람들이 좋아하는 숫자를 모두 포함하는 경우의 최대 사람수를 구하는 문제

• 사람의 숫자는 n으로 주어진다.
• 각 사람이 좋아하는 숫자는, m개로 각 사람마다 숫자 m이 주어진다.
• 연속된 m개의 숫자가 이어서 주어진다.
• 숫자 k가 주어진다.
• 1부터 k까지의 숫자 배열중 d개를 선택했을때, 사람들이 좋아하는 숫자들을 모두 포함하는 경우에 결과값에 +1을 한다.
• 위의 연속된 m개의 숫자는 1과 k사이의 숫자이다.

1. 비트마스크를 활용하지 않는 경우

k개의 숫자중 각 사람들이 좋아하는 숫자가 있는지 계산하여야 한다.

#include <bits/stdc++.h>

using namespace std;

int n, d, k, cnt_max = INT_MIN;
vector<int> student[30001];
vector<int> vec_like(16);
int ch[16];

void DFS(int Level, int start) {
    if (Level == k) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            bool flag = true;
            for (int j = 0; j < student[i].size(); j++) {
                int count_n = count(vec_like.begin(), vec_like.end(), student[i][j]);
                if (count_n == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag == true) {
                cnt++;
            }
        }
        cnt_max = max(cnt, cnt_max);
    } else {
        for (int i = start; i <= d; i++) {
            ch[i] = 1;
            vec_like[Level] = i;
            DFS(i + 1, Level + 1);
            ch[i] = 0;

        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "rt", stdin);

    cin >> n >> d >> k;
    for (int i = 1; i <= n; i++) {
        int n_times;
        cin >> n_times;
        for (int j = 1; j <= n_times; j++) {
            int a;
            cin >> a;
            student[i].push_back(a);
        }
    }
    DFS(0, 1);
    cout << cnt_max;
    return 0;
}

• for (int j = 0; j < student[i].size(); j++) : k개의 숫자중 각 사람들이 좋아하는 숫자가 있는지 계산

2. 비트마스크를 활용하는 경우

k개의 숫자중 각 사람들이 좋아하는 숫자가 있는지 따로 계산하지 않는다.
비트마스크를 활용하여 시간복잡도를 줄인다.

#include <bits/stdc++.h>
using namespace std;

int n, d, k, res = INT_MIN;
int student[30001], arr_pow[16];
void DFS(int Level , int start, int bit) {
    if(Level == k) {
        int cnt = 0;
        for (int i=1; i<=n; i++) {
            if((student[i] & bit) == student[i]) cnt++;
        }
        res = max(res, cnt);
    }
    else {
        for (int i=start; i<=d; i++) {
            DFS(Level + 1, i + 1, bit + arr_pow[i]);
        }
    }

}
int main() {
    ios_base::sync_with_stdio(false);
    freopen("input.txt", "rt", stdin);
    cin >> n >> d >> k;
    arr_pow[1] = 1;
    for (int i = 2; i <= d; i++) arr_pow[i] = arr_pow[i - 1] * 2;
    for (int i=1; i<=n; i++) {
        int n_times;
        cin >> n_times;
        for (int j=1; j<=n_times; j++) {
            int num;
            cin >> num;
            student[i] += arr_pow[num];
        }
    }
    DFS(0, 1, 0);
    cout << res;

    return 0;
}

• if((student[i] & bit) == student[i]) cnt++ : 비트마스크를 이용하여, 포함여부를 계산한다.
• DFS(Level + 1, i + 1, bit + arr_pow[i]) : bit부분에 arr_pow[i]를 더함으로써 i에 해당하는 정수를 포함한다는 것을 저장한다.
• student[i] += arr_pow[num] : 비트마스크를 활용하기 위해서 2의 배수로 저장한다.