백준 1062번 가르침 C++

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

 

백트래킹으로 k개의 글자를 가르치는 경우를 전부 확인해보면 시간초과가 난다.

남극언어는 anta로 시작하고 tica로 끝난다고 했기 때문에 a,c,i,n,t는 무조건 배워야 한다.

그래서 저 글자들은 처음에 배웠다고 가정하고 시작한다. 그러면 글자를 가르치는 경우가 26Ck 에서 21Ck로 줄어서 통과된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, k;
vector<string> strs;
vector<char> v(26);
vector<bool> found;
vector<int> idxs;
set<char> s;

int ans = 0;

void BT(int idx, int cnt) {
    if (cnt >= k) {
        int _cnt = 0;
        for (auto a : strs) {
            bool canRead = true;
            for (int i = 0; i < a.length(); i++) {
                auto it = s.find(a[i]);
                if (it == s.end()) {
                    canRead = false;
                    break;
                }
            }
            if (canRead) _cnt++;
        }
        ans = max(ans, _cnt);
        return;
    }
    for (int i = idx; i < 26; i++) {
        if (found[i]) continue;
        found[i] = true;
        s.insert(v[i]);
        BT(i + 1, cnt + 1);
        found[i] = false;
        s.erase(v[i]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    strs = vector<string>(n);
    found = vector<bool>(26, false);
    for (int i = 0; i < 26; i++) {
        v[i] = i + 97;
    }
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        string sub = str.substr(4, str.length() - 8);
        strs[i] = sub;
    }
    if (k >= 5) {
        found['a' - 97] = true;
        found['c' - 97] = true;
        found['i' - 97] = true;
        found['n' - 97] = true;
        found['t' - 97] = true;
        s.insert('a');
        s.insert('c');
        s.insert('i');
        s.insert('n');
        s.insert('t');
        BT(0, 5);
    }
    cout << ans;
}