[백준 1062] 가르침

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

 

모든 단어는 anta로 시작하고 tica로 끝난다. 이미 a, n, t, i, c를 사용했으니 K가 5보다 작으면 검사할 필요 없이 0을 출력하면 된다. 단어의 수는 8 ~ 15이며 여기서 접두사, 접미사를 빼면  0 ~ 7글자가 되는데 여기서  a, n, t, i, c 를 제외한 K - 5개의 글자를 검사해야 한다.

 

a, n, t, i, c를 제외한 알파벳 중에 어떤 알파벳이 등장하였는지 센다. 총 21글자가 올 수 있으며 해당 문자에서 K - 5개를 선택해(Back Tracking) 해당 문자를 만들수 있는지 없는지(Bit Mask) 검사하면 된다

 

#include <iostream>
#include <set>
using namespace std;
int N, K, M, MAX;
int arr[51];
char selected[7];
char list[21];
set<char> s;
void backTrack(int idx, int cnt) {
    if(cnt == K) {  // K개 골랐으면
        int alphabet = 532741;  // antic
        for(int i = 0; i < K; i++) {
            alphabet |= 1 << (selected[i] - 'a');
        }
        int get = 0;
        for(int i = 0; i < N; i++) {
            if((arr[i] & alphabet) == arr[i]) {
                get++;
            }
        }
        MAX = max(MAX, get);
        return;
    }
    for(int i = idx; i < M; i++) {
        selected[cnt] = list[i];
        backTrack(i + 1, cnt + 1);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> K;
    if(K < 5) {
        cout << 0;
    } else {
        for(int i = 0; i < N; i++) {
            string str;
            cin >> str;
            for(char j : str) {
                if(j == '\0') break;
                arr[i] |= 1 << (j - 'a');
                if(j == 'a' || j == 'n' || j == 't' || j == 'i' || j == 'c') continue;
                if(!s.count(j)) {
                    s.insert(j);
                }
            }
        }
        M = 0;
        for(char c : s) {
            list[M] = c;
            M++;
        }
        K -= 5;
        MAX = 0;
        if(K >= M) {
            cout << N;
        } else {
            backTrack(0, 0);
            cout << MAX;
        }
    }
}