[C++] 백준 1062번 가르침

비트마스크 문제입니다.

알파벳에 대하여 비트마스크로 처리합니다.
0x3FFFFFF  (11 1111 1111 1111 1111 1111 1111)

각 텍스트에 대해서 비트마스크 처리해줍니다.

배울 수 있는 알파벳 개수에 따라 가능한 조합들을 DFS로 확인하였습니다.
각 조합에서 텍스트와 비트마스크 연산을 통해 문자조합이 텍스트를 포함하는 경우 카운트를 증가해줍니다.

ex)
텍스트가 acd 이면 1101입니다

배울 수 있는 알파벳은 0으로 처리를 합니다.
배울 수 있는 알파벳이 abcdf이면
11 1111 1111 1111 1111 1101 0000입니다.

텍스트 (acd)
00 0000 0000 0000 0000 0000 1101

배울 수 있는 알파벳 (abcdf)
11 1111 1111 1111 1111 1101 0000

두개를 &연산을 처리 했을 때 0으로 덮는 경우 가능한 경우로 판단하였습니다.
00 0000 0000 0000 0000 0000 0000

*비트마스크로 하지 않으면 시간초과가 발생합니다.

 

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

vector<int> text;
int n, k;
int bit[50];
int result = 0;

void DFS(int deep, int location, int bit)
{
  for (int i = location + 1; i < 26; ++i)
  {
    int tempBit = bit ^ (1 << i);
    if (k == deep + 1)
    {
      int count = 0;
      for (int i = 0; i < text.size(); ++i)
      {
        int compareBit = text[i] & tempBit;
        if (compareBit == 0x0000000)
        {
          ++count;
        }
      }
      result = max(result, count);
      continue;
    }
    DFS(deep + 1, i, tempBit);
  }
}

int main(int argc, char *argv[])
{
  string s;

  cin >> n >> k;

  for (int i = 0; i < n; ++i)
  {
    cin >> s;
    text.push_back(0);
    for (int j = 0; j < s.length(); ++j)
    {
      text[i] = text[i] | (1 << (s[j] - 97));
    }
  }

  DFS(0, -1, 0x3FFFFFF);

  cout << result;

  return 0;
}