[1062] 가르침

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

1062번: 가르침

<문제>

TSP문제와 비슷하게 비트마스킹+백트래킹으로 해결이 가능하다.

비트마스크를 사용하지않아도 TLE가 나오는 문제는 아니다.

 

모든 단어의 시작과 끝이 정해져있다는 문제 조건에 근간하여

a c i n t    5글자를 먼저 배우고 시작을 하도록 구현하면 조금 더 최적화가 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, k, w[51];
int learn, ans;
void f(int idx, int depth) {
    if (depth == k) {
        int score = 0;
        for (int i = 0; i < n; i++) {
            if ((w[i] & learn) == w[i]) score++;
        }
        ans = max(score, ans);
    }
    for (int i = idx; i < 26; i++) {
        if ((learn & (1 << i)) != 0) continue;
        learn |= (1 << i);
        f(i + 1, depth + 1);
        learn &= ~(1 << i);
    }
}
int main(void) {
    int i, j;
    cin >> n >> k;
    for (i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (j = 0; j < s.length(); j++) w[i] |= (1 << (s[j] - 'a'));
    }
    if (k < 5) {
        cout << "0";
        return 0;
    }
    if (k == 26) {
        cout << n;
        return 0;
    }
    learn |= 1 << ('a' - 'a');
    learn |= 1 << ('c' - 'a');
    learn |= 1 << ('i' - 'a');
    learn |= 1 << ('n' - 'a');
    learn |= 1 << ('t' - 'a');
    f(0, 5);
    cout << ans;
    return 0;
}