[BOJ] 1062 : 가르침

풀이

브루트 포스 / 비트마스크

비트마스크로 사용할 단어 모든 조합을 만들어서 전체탐색으로 그냥 풀었을때 328ms

for (int i = 0; i < (1 << 26); i++)

for문 범위를 i<(1«21)로 좁히고 배열에 보정치를 넣어서 풀었을때 272ms

int arr[26] = { 0 };
            int bonus = 0;
            for (int j = 0; j < 26; j++) {
                if (j == 0 || j == 2 || j == 8 || j == 13 || j == 19) {
                    arr[j] = 1;
                    bonus++;
                }
                else {
                    if (i&(1 << (j-bonus))) {
                        arr[j] = 1;
                    }
                }
            }

각 단어를 살펴볼 필요없으므로 입력받을 때 부터 bit or연산으로 마스크로 저장하고,

  for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (char x : str) {
            words[i] |= (1 << (x - 'a'));
        }
    }

배열 대신 mask로 숫자를 만든 후 words랑 비교해서 판정했을때 80ms가 나왔다.

          for (int j = 0; j < n; j++) {
                if ((words[j] & ((1 << 26) - 1 - mask)) == 0) {
                    sum++;
                }
            }

단순히 조합을 짜는데 비트마스크를 사용했었는데,

이게 정말 비트마스크의 진가인것같다. 3배이상 계산속도가 빨라진다니 훌륭한 스킬이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    cin >> n >> k;
    //a,n,t,i,c
    if (k < 5) {
        cout << 0;
        return 0;
    }
    int ans = 0;
    vector<int> words(n);
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (char x : str) {
            words[i] |= (1 << (x - 'a'));
        }
    }
    
    for (int i = 0; i < (1 << 21); i++) {
            int cnt = 0;
            for (int j = 0; j < 21; j++) {
                if (i&(1 << j))
                    cnt++;
            }
            if (cnt != k-5)
                continue;

            //mask 만들기
            int mask = 0;
            int bonus = 0;
            for (int j = 0; j < 26; j++) {
                if (j == 0 || j == 2 || j == 8 || j == 13 || j == 19) {
                    mask |= (1 << j);
                    bonus++;
                }
                else {
                    if (i&(1 << (j-bonus))) {
                        mask |= (1 << j);
                    }
                }
            }
            //만든알파벳으로 단어들을 만들 수 있는지 비트마스크로 확인
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ((words[j] & ((1 << 26) - 1 - mask)) == 0) {
                    sum++;
                }
            }
            if (ans < sum)
                ans = sum;
    }
    cout << ans;
    return 0;
}

Written on May 2, 2019