백준 BOJ(1062) 가르침

문제 :

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

1062번: 가르침

 

풀이 :

 

anta와 tica는 무조건 들어가야 하므로 최소 k가 5개는 필요하다 5개가 되지 않는다면 0을 리턴하자

 

5개가 넘는다면 a n t i c는 true 처리를 해주고 나머지 21개의 알파벳 중 k-5개를 고른다.

 

k-5개를 골랐다면 check만을 통해 단어를 만들 수 있는지 확인하고 최대 값을 구해준다.

 

코드 ( C++ )

 

	#include <cstring>
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <string>
	using namespace std;
	// a n t i c
	bool check[26];
	vector<string> v;
	int ans;
	void solve(int begin, int cnt)
	{
	if (cnt == 0) {
	int sum = 0;
	//비교해서 최댓값 구한다
	for (int i = 0; i < v.size(); ++i) {
	bool ch = true;
	for (int j = 0; j < v[i].size(); ++j) {
	int temp = v[i][j] - 'a';
	if (check[temp] == 0) {
	ch = false;
	break;
	}
	}
	if (ch) sum++;
	}
	ans = max(ans, sum);
	return;
	}
	for (int i = begin + 1; i < 26; ++i) {
	if (check[i]) continue;
	check[i] = true;
	solve(i, cnt - 1);
	check[i] = false;
	}
	}
	int main()
	{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
	string s;
	cin >> s;
	v.push_back(s);
	}
	if (k < 5) {
	cout << 0 << "\n";
	return 0;
	}
	k -= 5;
	check['a' - 'a'] = true;
	check['n' - 'a'] = true;
	check['t' - 'a'] = true;
	check['i' - 'a'] = true;
	check['c' - 'a'] = true;
	solve(-1, k);
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub