문제

N개에 단어중에서 K개의 알파벳을 선택했을때 K개 알파벳으로 표현가능한 최대 단어수를 찾는 문제다.

a n t i c 라는 단어는 필수적으로 들어가서 5개의 단어는 먼저 선택할수있다.

26개 알파벳중 K개를 골라 순차적으로 체크해볼수있는데
시간복잡도를 생각하면 21Ck (k는21보다 작은데 10일때 최대이므로 21C10=352,716 즉 30만이다) 경우에

체크연산 N글자수 5015 => 750이므로 총 264,537,000 2초가까이 나오는데
체크 연산 중간에 실패하면 탈출하므로 실제 계산은 그 정도까지 나오진 않았다.

code

/*
백준 1062
anta  tica
a n t i c 5글자
*/
#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;

vector<string> words;
map<char,char> knows;
char alphabet[21] = { 'b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z'};

int N, K,ans=0;

void check() {
	int cnt = 0;
	for (int wordIdx = 0; wordIdx < words.size(); wordIdx++) {
		bool isOk = true;
		// 한 단어씩 체크
		for (int i = 0; i < words[wordIdx].size(); i++) {
			// 못찾으면
			if (knows.find(words[wordIdx][i]) == knows.end()) {
				isOk = false;
				break;
			}
		}
		if (isOk) cnt++;
	}
	ans = (cnt > ans) ? cnt : ans;
}


void pickApha(int alphaIdx,int pickNum) {
	if (pickNum == K - 5) {
		// check
		check();
		return;
	}
	if (alphaIdx+1 >= 21) return;

	// 선택하거나
	knows.insert({ alphabet[alphaIdx + 1], alphabet[alphaIdx + 1] });
	pickApha(alphaIdx + 1, pickNum + 1);
	knows.erase(alphabet[alphaIdx + 1]);

	// 뛰어넘기
	pickApha(alphaIdx + 1, pickNum);
}

int main(void) {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		words.push_back(str);
	}
	knows.insert({ 'a','a' });
	knows.insert({ 'n','n' });
	knows.insert({ 't','t' });
	knows.insert({ 'i','i' });
	knows.insert({ 'c','c' });

	// K가 5미만일때는 0
	if (K < 5) {
		cout << 0;
		return 0;
	}

	// 알파벳 26개 - 5개 => 21개 중 2개를 뽑는다
	// 즉 21개 중 k-5개를 뽑는다
	// 0개부터 시도
	pickApha(-1, 0);
	
	cout << ans;
}