백준 1062번 가르침

문제 링크

문자열을 하나하나 다 만들어서 비교할 필요는 없다. 어떤 글자를 배웠는지 비트로 표현한다.

i 번째 글자를 배운다는 것을 다음과 같이 표현할 수 있다.

int cur = cur | (1<<i);

지금까지 배운 글자들 cur로 단어 x를 읽을 수 있는지 어떻게 알 수 있을까?

if (((cur^x)&x) == 0) can++;

xor 연산을 통해 지금까지 배운 글자와 단어에 포함된 글자 중 일치하지 않는 글자를 찾고, 이 글자가 x에 하나라도 존재하면 단어를 읽을 수 없다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, k;
int ans = 0;
vector<int> v;

void solve(int cur, int cnt, int idx) {
    if (cnt == k) {
        int can = 0;
        for (auto x : v) {
            if (((cur^x)&x) == 0) can++;
        }
        ans = max(ans, can);
        return;
    }

    for (int i = idx+1; i < 26; i++) {
        if (cur&(1<<i)) continue;
        solve(cur|(1<<i), cnt+1, i);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int x = 0;
        for (auto c : s) {
            x = x|(1<<(c-'a'));
        }
        v.push_back(x);
    }

    if (k < 5) {
        cout << 0 << '\n';
        return 0;
    }

    int start = 0;
    string s = "antic";
    for (auto c : s) {
        start = start|(1<<(c-'a'));
    }
    solve(start, 5, 0);

    cout << ans << '\n';

    return 0;
}

모든 단어에 'a', 'n', 't', 'i', 'c' 가 들어가기 때문에 처음부터 고려해주었다.