[백준] 1062번 가르침

1062번: 가르침

조합을 이용해서 푸는 완전 탐색 문제이다.

조합의 경우의 수를 줄이려고 입력받을 때

a, c, i, n, t를 제외시키고

중복되는 단어들도 제외시키고

배울 수 있는 단어들을 따로 만들어놓고 비교하니 시간 초과가 나왔었다.

이렇게 제외시켜서 하는 과정이

그냥 전부 비교하는 방법보다 더 오래 걸린다는 것이다.

그래서 갈아엎고 다시 짰다.

 

각 단어는 "a, c, i, n, t"를 무조건 포함하므로

K가 5 미만일 때는 어떤 단어도 읽을 수 없기 때문에 0을 출력한다.

그 외의 경우에는

단어를 순서 상관없이 K-5개 뽑았을 경우에

N개의 단어들 중에서 최대한 몇 개 읽을 수 있는지를 체크해준 뒤

최댓값을 출력해주면 된다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N, K, tmp, res, cnt;
bool nope = false;
bool visited[26] = { false };
string a, alphabet[50];
void combination(int idx) { //word의 알파벳 중 K개를 뽑는다
	if (cnt + 5 == K) {
		for (int n = 0; n < N; n++) {
			for (int i = 4; i < alphabet[n].size() - 4; i++) {
				if (!visited[alphabet[n][i] - 'a']) {
					nope = true;
					break;
				}
			}
			if (!nope) tmp++;
			else nope = false;
		}
		res = max(res, tmp), tmp = 0;
		return;
	}
	for (int i = idx; i < 26; i++) {
		if (!visited[i]) {
			visited[i] = true, cnt++;
			combination(i + 1);
			visited[i] = false, cnt--;
		}
	}
}
int main() {
	cin >> N >> K;
	for (int n = 0; n < N; n++) cin >> alphabet[n];
	visited[0] = visited['c' - 'a'] = visited['i' - 'a'] = visited['n' - 'a'] = visited['t' - 'a'] = true;
	if (K >= 5) combination(0); //최소 다섯 글자를 알아야한다
	cout << res;
	return 0;
}