[C++] 백준 1062번: 가르침 - Bitmask

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

1062번: 가르침

 

비트연산자를 공부한 후 가장 처음 도전한 문제

배우고 응용은 처음이라그런지 상당히 코드는 더럽지만

그래도 어느정도 알겠다..

 

계속 틀린 이유는 k보다 v.size()가 작은 경우를 고려하지 않아서 틀렸고,

16번째 줄 구현이 너무 어려웠다.

 

내 생각에는 (1 << p) & t == (1 << p) 이런 느낌의 코드를 생각했으나 (포함 관계)

실제로는 계속 false가 반환되는 바람에 어디가 문제인지 찾지도 못했다.

더 공부해서 해당 부분을 다시 짜봐야겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string arr[51];
int n, k, ans, t;
bool check[26];
vector<char>v;
void track(int u, int cnt){
    if(cnt==k || u==v.size()){
        int res=0;
        for(int i=0; i<n; i++){
            bool c=true;
            for(int j=0; j<arr[i].length(); j++){
                int p=(arr[i][j]-'a');
                if((1<<p)&t) continue;
                else{
                    c=false;
                    break;
                }
            }
            if(c) res++;
        }
        ans=max(ans, res);
        return;
    }
    for(int i=u; i<v.size(); i++){
        int l=v[i]-'a';
        if(!check[l]){
            check[l]=true;
            t|=(1<<l);
            track(i+1, cnt+1);
            check[l]=false;
            t&=~(1<<l);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        for(int j=0; j<arr[i].size(); j++) {
            if(arr[i][j]!='a' && arr[i][j]!='n' && arr[i][j]!='t' && arr[i][j]!='i' && arr[i][j]!='c') v.push_back(arr[i][j]);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    if(k<5){
        cout << 0;
        return 0;
    }
    t|=(1<<('a'-'a'));
    t|=(1<<('n'-'a'));
    t|=(1<<('t'-'a'));
    t|=(1<<('i'-'a'));
    t|=(1<<('c'-'a'));
    check[0]=true;
    check['n'-'a']=true;
    check['t'-'a']=true;
    check['i'-'a']=true;
    check['c'-'a']=true;
    track(0, 5);
    cout << ans;
}