1062번 가르침

제목대로 가르침받았다.. 후 너무 어렵당 다시 풀어봐야겠다.
정리할게 너무 많다.

우선 비트마스크는 보통 모든 부분수열을 찾을 때 사용한다. 따라서 선택가능한 K개의 알파벳중 일일이 알파벳을 선택했는지의 여부는 재귀를 통해 해결한다.

1. 해당 문제를 일일이 26개의 알파벳 중에서 K개를 고르고, N개의 단어중에서(최대 L길이) 고른 알파벳으로 이루어 졌는지를 확인하려면 2^26 N L의 시간복잡도가 걸린다. 당연히 시간초과가 난다.
2. 문제의 조건 중에서 a, n, t, i, c의 알파벳은 필수로 들어가야 한다. 따라서 그 외에 21개의 알파벳을 골라야한다. 따라서 2^21 N L의 시간복잡도가 걸린다. 이것도 시간초과가 난다.
3. 어디서 시간복잡도를 줄일 수 있는지 살펴보자. 일일이 알파벳을 고르고 말고를 줄일 순 없다. 브루트포스이기 때문이다(이전에도 말했듯이 어지간한건 거의..). 들어온 각각의 단어도 당연히 일일이 확인해야 한다. 그렇다면 줄일 수 있는 곳은 각 단어에 해당하는 문자를 읽을때이다. 이때! 비트마스크를 사용한다. 비트마스크는 시간복잡도가 O(1)이기 때문에 개꿀이다. 이제 '단어가 입력될 때', 비트마스크로 저장한다. 그리고 재귀를 돌때마다 '알파벳을 배울때'도 비트마스크를 사용한다. 마지막으로 '단어에 배우지 않은 알파벳이 있는지'에 비트마스크를 사용한다. 이때는 [(int)단어 & ~L] 로 사용한다. ~L를 구할때는 1111 - 1101(L) 이런식으로 ~L을 구하는데, 1111은 확장하여 (1<<26)-1로 설정하고 L을 빼준다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int count(int mask, vector<int> &words) {
	//알파벳 z까지 확인했으니 이제 읽을 수 있는 단어가 있는지 확인해보자
	int cnt = 0;
	for (int i = 0; i < words.size();i++) {
		if ((words[i] & (1 << 26) - 1 - mask) == 0) cnt++;
	}

	return cnt;
}

int DFS(int index, int k, int mask, vector<int> words) {
	if (k < 0) return 0;//why 0?
	if (index == 26) return count(mask, words);//마지막 알파벳까지 왔으면 count세고 와라
	int ans = 0;
	//이번 알파벳은 선택하고, 재귀 다녀오렴
	int t1 = DFS(index + 1, k - 1, mask | (1 << index), words);
	if (ans < t1) ans = t1;
    
	//이제 안고르고 재귀 다녀와보렴
	//그런데, a n t i c 는 꼭 골라야하는거 알지? 얘네 안고르면 그냥 통과시킬겡ㅎ
	if (index != 'a' - 'a' && index != 'n' - 'a' && index != 't' - 'a' && index != 'i' - 'a' && index != 'c' - 'a') {
		t1 = DFS(index + 1, k, mask, words);
		if (ans < t1) ans = t1;
	}
	return ans;
}
int n, m;
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("in1.txt", "rt", stdin);
	cin >> n >> m;
	vector<int> words(n);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (char j : s) {
			// |=을 통해 중복을 제외하고 넣기 가능
			words[i] |= (1 << (j - 'a')); //글자의 중복을 제거하고 비트마스킹
		}
	}
	cout << DFS(0, m, 0, words) << '\n';
	return 0;
}