[BOJ] 1062 가르침 C++

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

1062번: 가르침

 

비트마스킹을 활용한 브루트 포스 문제. 처음 보는 유형이라서 다른 분의 코드를 좀 참조하였다.  설명은 주석에...

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int N,K;
int ans=0;
int word[50];
string s;
void DFS(int n,int start,int BIT){
    //순서가 중요하지 않으므로 start를 이용해서 경우의 수를 줄여주자
    if(n==K-5){
        int cnt=0;
        for(int i=0;i<N;i++){
            //BIT안에 있는 문자로 word안에 있는 문자들을 다 표현 할 수 있으면 cnt++
            if((word[i]&BIT)==word[i]) cnt++;
        }
        ans=max(ans,cnt);
        return;
    }
    for(int i=start;i<26;i++){
        if(!(BIT&(1<<i))){ //해당 알파벳이 존재하지 않는다면
            BIT|=1<<i; // 그 알파벳을 넣어준다
            DFS(n+1,i,BIT);
            BIT&=~(1<<i); // 나올 때는 넣어 준 알파벳을 제거한다
        }
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>s;
        //문자를 모두 받는 것이 아니라 word에 문자가 가지고 있는 알파벳 정보들만 넣어준다.
        for(int j=0;j<s.size();j++) word[i]|=1<<(s[j]-'a');
    }
    if(K<5){
        //5보다 작으면 anta와 tica를 읽지 못하므로 0출력
        cout<<0;
        return 0;
    }
    if(K==26){
        //26이면 모든 알파벳을 가르칠 수 있으므로 모든 단어를 읽을 수 있다
        cout<<N;
        return 0;
    }
    int BIT=0;
    //필수적으로 배워야 할 정보 저장
    BIT|=1<<('a'-'a');
    BIT|=1<<('n'-'a');
    BIT|=1<<('t'-'a');
    BIT|=1<<('i'-'a');
    BIT|=1<<('c'-'a');
    DFS(0,0,BIT);
    cout<<ans;
    return 0;
}