백준 1062 C++

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

 

이 문제에서 제일 고민했던 부분은 배운 알파벳 선택을 어떻게 할까였다.

배우는 알파벳 개수는 정해져있기 때문에 재귀적으로 개수가 맞으면 그때 배운 알파벳에 따라서 몇개의 단어를 배울 수 있는지 count했다.

 

#include <bits/stdc++.h>

using namespace std;

//antic -> acint -> 1 3 9 14 20 -> 0 2 8 13 19

int n, k;		//n은 단어, k는 char
int result = 0;
int learn = (1 << 0) + (1 << 2) + (1 << 8) + (1 << 13) + (1 << 19);		//5개 배운 상태
string s;
vector<int> v;


void learnAlpha(int a, int startIndex, int count) {
	if (count == k) {
		int c = 0;
		for (auto i : v) {
			if ((i & a) == i) {		//i라는 숫자와 현재 배운 숫자의 비트가 모두 동일해서 i라는 단어를 배울 수 있을 때
				c++;
			}
		}

		//for (int i = 0; i < 26; i++) {			//배운 알파벳 출력
		//	if (a & (1 << i)) cout << (char)(i + 'a') << " ";
		//}
		//cout << "learn num : " << a << "  c : " << c << "\n";
		result = max(result, c);
		return;
	}

	for (int i = startIndex; i < 26; i++) {
		if (a & (1 << i)) continue;		//이미 해당 비트에 해당하는 알파벳을 배웠으면 다시 배우지 않는다.


		a = a + (1 << i);	//i번째 비트를 켜준다.
		learnAlpha(a, i, count + 1);
		a = a - (1 << i);	//i번째 비트에 해당하는 알파벳을 안배웠을 경우도 생각해야하기 때문에 원복시킨다.
	}
}


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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {			//v에 string을 int로 바꿔서 넣음
		cin >> s;
		int temp = 0;
		for (int j = 0; j < s.size(); j++) {
			if (temp & (1 << (s[j] - 'a'))) continue;	//s[j]에 해당하는 알파벳 순서에 대한 비트가 켜져있다면 continue
			temp += (1 << s[j] - 'a');			//비트가 안켜져있다면 +해줘서 켜준다.
		}
		v.push_back(temp);
	}

	//배운 알파벳 선택이... 어떻게 해야할까?
	//
	if (k >= 5) {
		learnAlpha(learn, 1, 5);			//learn을 배운 숫자로 넘기고 1부터하는 이유는 a는 이미 배운상태이기 때문 5는 이미 5개를 배웠기 때문이다.
	}

	cout << result;
}