BOJ : 1062 가르침

---

[BOJ 1062(G4)리뷰]

처음에 문제 이해를 잘못해서 푸는데 시간을 오래 썼다.

문제의 조건을 보면 모든 단어는 "anta"로 시작되고 "tica"로 끝난다고 하였으니 K개의 글자에는 최소 "a,n,t,i,c"의 알파벳이 필요하다. 즉, K가 5미만 이라면 단 한개의 단어도 읽을 수 없다.

이 조건을 생각하며 나머지 알파벳에 대하여 완전탐색을 실시하면 된다. 이미 사용한 알파벳에 대하여 방문처리를 하고 남은 알파벳에 대해 완전탐색을 수행해 알파벳의 개수가 K개가 되었을때 읽을 수 있는 단어를 카운팅하고 최대값을 계산해주면 된다.

문제를 이해하고 나면 전형적인 백트래킹 문제로 바뀌게 된다. 그리고 알파벳을 체크하는 배열은 ASCII코드 값을 이용하여 관리하면 편하다.

/*
	21.01.11
	BOJ : 1062 가르침 (https://www.acmicpc.net/problem/1062)
	백트래킹
*/
#include <bits/stdc++.h>
using namespace std;


int idx[26] = { 0 };

int N, K;
int selectedCount = 0;
int ans = 0;
vector <string> word;

void dfs(int index) {
	if (selectedCount == K) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			string cur = word[i];

			int len = cur.size();
			bool check = true;
			for (int j = 0; j < len; j++) {
				if (idx[cur[j] - 'a'] == 0) {
					check = false;
					break;
				}
			}

			if (check)
				cnt++;
		}

		ans = max(ans, cnt);
		return;
	}

	for (int i = index; i < 26; i++) {
		if (idx[i]) continue;
		idx[i] = 1;
		selectedCount += 1;
		dfs(i);
		idx[i] = 0;
		selectedCount -= 1;
	}
	
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		string temp;
		cin >> temp;
		word.push_back(temp);
	}

	if (K < 5) {
		cout << 0;
		return 0;
	}

	

	idx['a' - 'a'] = 1;
	idx['c' - 'a'] = 1;
	idx['i' - 'a'] = 1;
	idx['n' - 'a'] = 1;
	idx['t' - 'a'] = 1;
	

	for (int i = 0; i < 26; i++) {
		if (idx[i]) continue;
		selectedCount = 5;
		dfs(i);
	}
	cout << ans;
	return 0;
}