백준1062 - 가르침

www.acmicpc.net/problem/1062

1062번: 가르침

백트래킹을 이용하여 구현하였다. a, n, t, i, c는 무조건 주어지므로 5개 이상 배우지 않으면 단어를 배울 수 없게 된다. 따라서 5개 이하는 탐색을 하지 않고 0을 출력한다. 26개 경우는 모든 알파벳을 배우므로 단어를 모두 읽을 수 있다. 따라서 단어의 개수를 출력한다. 그 외의 경우는 a, n, t, i, c의 갯수를 주어진 K에서 빼서 백트래킹을 할 때 마다 탐색을 한다. 그러면 처음에 5개는 방문한 채로 탐색을 하니까 시간초과를 조금이나마 줄일 수 있다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, ans = 0;
string s;
vector<string> v;
bool visit[26];

void dfs(int x, int cnt) {
    if(cnt == K) {
        int temp = 0;
        for(auto t : v) {
            bool check = true;
            for(int i = 0; i < t.size(); i++) {
                if(!visit[t[i] - 'a']) {
                    check = false;
                    break;
                }
            }
            if(check) {
                temp++;
            }
        }
        ans = max(ans, temp);
        return;
    }
    
    for(int i = x; i < 26; i++) {
        if(!visit[i]) {
            visit[i] = true;
            dfs(i + 1, cnt + 1);
            visit[i] = false;
        }
    }
}

int main() {
    cin >> N >> K;
    for(int i = 0; i < N; i++) {
        cin >> s;
        s = s.substr(4, s.size());
        s = s.substr(0, s.size() - 4);
        v.push_back(s);
    }
    
    visit['a' - 'a'] = true;
    visit['n' - 'a'] = true;
    visit['t' - 'a'] = true;
    visit['i' - 'a'] = true;
    visit['c' - 'a'] = true;
    
    if(K < 5) {
        cout << ans;
    }
    else if(K == 26) {
        cout << N;
    }
    else {
        K = K - 5;
        dfs(0, 0);
        cout << ans;
    }
    
    return 0;
}