백준 / 1062 가르침

www.acmicpc.net/problem/1062

1062번: 가르침

알파벳을 배운 남극 학생들이 어떤 조합의 알파벳일 때 가장 많은 단어를 배우는지에 대한 문제입니다.

처음에는 가르친 알파벳 순으로 bit로 표현한 뒤 입력 단어도 bit로 표현하여 비트마스킹의 xor 결과가 0이냐 아니냐로 나눠서 생각했지만, 이것은 더 많이 배우고 입력 단어가 짧은 경우 0은 아니지만 모든 입력 단어를 읽을 수 있었습니다. 

 

그래서 dfs를 이용해 해당 위치의 알파벳을 배웠는지 유무와 cnt 값을 이용해 해당 값이 k-5개와 일치할 때마다 제대로 배웠는지를 체크하도록 하였습니다. (5개 빼는 이유는 a, t, n, i, c는 반드시 알아야하는 알파벳이기 때문에)

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<string>
#include<bitset>
#include<algorithm>

using namespace std;

int n, k;
vector<string>words; // 단어들 모음
bool learn[26]; // 알파벳 순으로 배웠는지 유무
int result = 0;

void init()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		words.push_back(s);
	}

	// a, t, i, n, c는 무조건 배워야함
	learn[0] = true;
	learn['t' - 'a'] = true;
	learn['i' - 'a'] = true;
	learn['n' - 'a'] = true;
	learn['c' - 'a'] = true;
}

// idx : 알파벳 위치, cnt : 배운 알파벳 개수
void dfs(int idx, int cnt)
{
	// k개의 글자를 다 배운 경우
	if (cnt == k) {
		int res = 0;
		for (int i = 0; i < n; i++) {
			string s = words[i];
			bool check = true;

			// 처음 4글자, 마지막 4글자는 고정
			for (int j = 4; j < s.size() - 4; j++) {
				int num = s[j] - 'a';

				// 안 배운 글자 존재하는 경우
				if (learn[num] == false) {
					check = false;
					break;
				}
			}

			if (check == true)
				res++;
		}
		result = max(result, res);
	}

	// 아직 다 안 배운 경우
	else {
		for (int i = idx; i < 26; i++) {
			if (learn[i] == false) {
				learn[i] = true;
				dfs(i, cnt + 1);
				learn[i] = false;
			}
		}
	}

	return;
}

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

	init();

	// a,n,t,i,c도 못배우는 경우
	if (k < 5) {
		cout << 0;
		return 0;
	}
	
	// a,n,t,i,c 를 제외한 k-5개 학습 시작
	k -= 5;
	dfs(0, 0);
	cout << result;
}