[백준] 1062 가르침

 

완전탐색을 통해 찾을 수 있는 문제다

모든 단어는 antc로 시작하고 tica로 끝나므로

최소 antic 문자는 배워야한다! 5개!!

 

그럼 알파벳 21개중에 내가 k-5개를 골라서

그 알파벳들로 최대로 배울 수 있는 문장수를 찾으면 된다!

 

비트를 통해 알파벳을 고르고 하나하나 확인해보자!

 

소스코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k,ans;
int arr[22];
bool alpha[26];
string s[55];
 
int solve(){
    int ret=0;
    for(int i=0;i<n;i++){
        bool c=true;
        for(int j=0;j<s[i].size();j++){
            if(!alpha[s[i][j]-'a']){
                c=false; break;
            }
        }
        if(c) ret+=1;
    }
    return ret;
}
 
int main(){
    int cnt=0;
    for(int i=0;i<26;i++){
        char c = i+'a';
        if(c=='a' || c=='n' || c=='t' || c=='i' || c=='c') continue;
        arr[cnt++] =i;
    }
 
    scanf(" %d %d",&n,&k);
    for(int i=0;i<n;i++){
        cin>>s[i];
        string t="";
        for(int j=0;j<s[i].size();j++){
            char c = s[i][j];
            if(c=='a' || c=='n' || c=='t' || c=='i' || c=='c') continue;
            t+=c;
        }
        s[i]=t;
    }
    k-=5;
    for(int i=0;i<(1<<cnt);i++){
        int tc=0;
        memset(alpha,0,sizeof(alpha));
        for(int j=0;j<cnt;j++){
            if(i&(1<<j)) {
                tc++; alpha[arr[j]]=true;
            }
        }
        if(k !=tc) continue;
        ans = max(ans,solve());
    }
    printf("%d\n",ans);
}