[백준]1062_가르침

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

Solved

✔ 남극언어의 모든 언어는 "anta"로 시작해 "tica"로 끝나므로 가르쳐야 하는 k개의 글자는 a,n,t,i,c가 있어야 한 글자는 읽을 수 있다.
✔ 그러므로 k가 5미만 일 땐 출력은 항상 0이다.
✔ 그렇다면 유의미한 답은 k가 5 이상일 때, 21개의 알파벳(26-5)의 boolean 값을 비교하여 답을 구하면 된다. 이 경우 21^2==441로 충분히 완전탐색이 가능하다.
✔ DFS로 21Ck(combination)를 구현했다.

using namespace std;
#include <iostream>
#include <vector>

int n;//남극언어의 단어 수
int k;//가르칠 글자 수.
bool alphabet[26];
vector<string> v;//단어 목록
int answer = 0;

void solution() {
	input();
	if (k < 5) {
		cout << "0\n";
		return;
	}
	k -= 5;
	alphabet['a'-'a'] = true;
	alphabet['n' - 'a'] = true;
	alphabet['t' - 'a'] = true;
	alphabet['i' - 'a'] = true;
	alphabet['c' - 'a'] = true;
	dfs(0, 0);
	cout << answer << '\n';
}

void input() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		v.push_back(s);
	}
}

void dfs(int cnt, int idx) {
	if (k == cnt) {
		int temp = ableNum();
		answer = answer > temp ? answer : temp;
		return;
	}

	for (int i = idx; i < 26; i++) {
		if (alphabet[i] == false) {
			alphabet[i] = true;
			dfs(cnt + 1, i + 1);
			alphabet[i] = false;
		}
	}
}

int ableNum() {
	int num = 0;
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].size(); j++) {
			if (alphabet[v[i][j] - 'a'] == false)
				break;
			if (j == v[i].size() - 1)
				num++;
		}
	}
	return num;
}