[백준 1062] 가르침

요구사항

1. 최대한 단어를 많이 알기 위한, 단어 K개 선택

2. 최대한 많이 아는 단어 출력

 

풀이

1. anta, tica는 알아야지 단어를 알 수 있다. 그러므로 최소 a n t a c 는 알아야지 단어를 알 수 있다.(k<5이하이면 아는 단어 0)

2. 26개의 단어르 알면 주어지는 단어 n개를 모두 알 수 있다.

3. a n t a c를 포함한 k개의 단어를 알 때, 알 수 있는 단어 cnt개가 정답이다.

21개중에 k-5개를 고르는 횟수 이므로 21C(k-5) 개의 가능성으로 브루트 포스 탐색한다

 

#include <stdio.h>
#include <map>
#include <algorithm>
//#include "Windows.h"
#include <iostream>
#include <vector>
#include <queue>
#include <list>

using namespace std;

struct go {
	int cnt;
	int index;
};
bool com(go a, go b) {
	if (a.cnt > b.cnt) return true;
	return false;
}
int alpha[50];
int n, k;
char input[50][20];
int ans = 0;
void dfs(int cnt, int now) {
	if (cnt + 5 == k) {
		int flag = 0;
		int count = 0;
		for (int i = 0; i < n; i++) {
			flag = 0;
			for (int j = 0; input[i][j] != 0; j++) {
				int now = (int)input[i][j] - 97;
				if (alpha[now] == 1) {
					continue;
				}
				else {
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
				count++;
			}
		}
		ans = max(ans, count);
		//	cout<<endl;
		return;
	}
	for (int i = now; i< 26; i++) {
		if (alpha[i] == 1) continue;
		alpha[i] = 1;
		dfs(cnt + 1, i);
		alpha[i] = 0;
	}
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%s", &input[i]);
	}

	if (k<5) {
		cout << 0 << endl;
		return 0;
	}
	if (k >= 26) {
		cout << n << endl;
		return 0;
	}
	alpha['a' - 97] = 1;
	alpha['c' - 97] = 1;
	alpha['i' - 97] = 1;
	alpha['t' - 97] = 1;
	alpha['n' - 97] = 1;
	dfs(0, 0);
	cout << ans << endl;
}