백준 1062 가르침(비트마스킹) - c++

문제링크 : https://www.acmicpc.net/problem/1062

문제설명

풀이

• 모든 단어들은 'anta'로 시작하고 'tica'로 끝나므로 'a c i n t' 이 5개는 꼭 배워야한다.
• 만약 k가 5보다 작다면, 단어에 필요한 글자 'a c i n t'를 모두 배울 수 없으므로 배울 수 있는 단어는 0개다.
• 입력된 단어들을 시작'anta', 끝 부분 'tica' 를 모두 소거 한후 비트연산을 할 수 있도록 변환한다.
  (a를 0으로 기준을 잡고, 변환)
• 'a c i n t'가 포함된 K개의 알파벳 조합을 DFS를 이용해 만들고, 만들어진 조합들을 각각 몇개의 단어를 만들 수 있는지 확인하고 가장 많이 만들수 있는 단어의 갯수를 출력한다.
  ('a c i n t')

코드

#include <iostream>
#include <string>

using namespace std;

int word[51];
int n, k, max_word =0;

void check(int num)                     // 조합으로 몇개의 단어를 만들수 있는지 체크
{
    int t =0;
    for (int i =0; i < n; i++)
    {
        if ((word[i] & num) == word[i])     // & 연산을 이용해 word[i]의 비트가 num 비트에 모두 포함 되는지 체크
        {
            t++;
        }
    }
    max_word = max(t,max_word);
}

void dfs(int start, int num, int now)               // dfs로 조합 만들기 
{
    if (now == k)
    {
        check(num);
        return ;
    }
    else
    {
        for (int i =start; i < 26; i++)
        {
            if(!(num & (1 << (i))))
            {
                num |= 1 << (i);
                dfs(i+1,num,now+1);
                num &= ~(1 << (i));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int learned = 0;
    
    cin >> n >> k;
     
    for (int i = 0; i < n; i++)
    {
        string temp;
        cin >> temp;
        for (int j = 4; j < temp.size()-4; j++)
        {
            word[i] |= (1 << (temp[j]-'a'));
        }
    }
     if (k < 5)
    {
        cout << "0\n";
        return 0;
    }
    if (k == 26)
    {
        cout << n << "\n";
        return 0;
    }

    // 조합 만들 때 시간 초과 방지로 'a n t i c'를 미리 체크 해놓기
	learned |= 1 << ('a'-'a');     
    learned |= 1 << ('n'-'a');
    learned |= 1 << ('t'-'a');
    learned |= 1 << ('i'-'a');
    learned |= 1 << ('c'-'a');

    dfs(1,learned,5);
    cout << max_word << "\n";
}

---

과거 소프트웨어 마에스트로 코딩테스트에서 비트마스킹 문제가 출제된적이 있다고 하여 공부를 하기시작 했지만, 최근 들어 비트마스킹 문제 푸는게 재미들려, 비트마스킹 문제만 주로 풀고있다...
dp 문제들도 많이풀어야하는데....