백준 1062번 가르침 ( C++ )

문제

https://www.acmicpc.net/problem/1062

 

해설

비트마스킹을 이용하는 문제

모든 경우의 수를 고려하기에는 너무 많음 => 재귀 호출을 이용한 제한된 호출

코드

// k가 0일 수 있음
#include <iostream>
#include <algorithm>
 
using namespace std;
int n, k, ret, word[54], basic;
string line;
 
void go(int idx, int num, int check)
{
  if (check == k)
  {
    int tmp = 0;
    for (int i = 0; i < n; i++)
    {
      if ((word[i] & num) == word[i])
        tmp++;
    }
    ret = max(tmp, ret);
    return;
  }
 
  for (int i = idx; i < 26; i++)
  {
    if (basic & (1 << i))
    {
      continue;
    }
    go(i + 1, num | (1 << i), check + 1);
  }
}
 
int main()
{
  cin >> n >> k;
  for (int i = 0; i < n; i++)
  {
    cin >> line;
    for (char a : line)
    {
      word[i] |= (1 << (a - 'a'));
    }
  }
  if (k < 5)
  {
    cout << 0;
    return 0;
  }
 
  basic |= (1 << ('a' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a')) | (1 << ('c' - 'a')) | (1 << ('i' - 'a'));
 
  go(1, basic, 5);
  cout << ret;
}