[BOJ-1062] 가르침(C++)

백준 1062 가르침

 

1062번: 가르침

 

문제 설명

 

 - 남극에 사는 김지민 선생님은 학생들에게 K개의 글자만 가르칠 수 있다.

 

 - 남극의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.

 

 - 학생들은 K개의 글자로만 이루어진 단어만 읽을 수 있다.

 

 - 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 구하라.

 

---

 

입력 값

 

 - 첫째 줄에 단어의 개수 N과 K가 주어진다.

 

 - N은 50보다 작거나 같은 자연수이다.

 

 - K는 26보다 작거나 같은 자연수 또는 0이다.

 

 - 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다.

 

 - 남극 언어의 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다.

 

 - 단어는 중복되지 않는다.

 

---

 

예제

 

---

 

 

문제 분석

 

 - 남극 언어의 모든 단어는 "anta" 와 "tica"로 끝난다.

   즉, 'a', 'n', 't', 'i', 'c' 는 반드시 들어가야 하는 글자라는 것이다.

 

 - K의 값은 26보다 작거나 같은 자연수 또는 0이고, 5글자는 반드시 들어가야 하기 때문에 

   K가 5이하인 경우 답은 반드시 0이 된다.

 

 - K가 5이상인 경우 반드시 들어가야 하는 단어를 제외한 21가지 단어 중 K-5 가지를 뽑는

   모든 경우를 살펴보고, 그 때 학생들이 읽을 수 있는 단어의 최대 개수를 구하면 된다.

 

 - 이때 최대 경우의 수를 살펴보면

   모든 단어 조합을 살펴보는 최대 경우의 수 21C10 = 약 35만

   단어 N개의 최대 값 50과, 각 단어는 최대 15자리이지만, 처음과 마지막 4자리는 고정이므로 7자리만 살펴보면 된다.

   즉, 모든 단어를 살펴보는 경우의 수는 50x7 = 350이다.

   결국 35만 x 350 = 약 1억2천이다.

 

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

// 기본 포함해야 하는 문자  'a','n','t','i','c' 를 제외한 문자들
char alpha[]{ 'b','d','e','f','g','h' ,'j' ,'k' ,'l' ,'m'  ,'o' ,'p' ,'q' ,'r' ,'s' ,'u' ,'v' ,'w','x','y','z' };
char baiscAlpha[] = { 'a','n','t','i','c' };

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;
	int result = 0;

	vector<string> checkString;

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

	// k가 5미만인 경우 무조건 0을 출력한다.
	if (K < 5) {
		cout << 0 << endl;
		return 0;
	}

	vector<int> comb(21);

	for (int i = 0; i < K-5; i++) {
		comb[21 - i - 1] = 1;
	}

	// 21C10 => 최대값
	// 35만
	do {
		bool nowAlpha[26];
		for (int i = 0; i < 5; i++) {
			nowAlpha[baiscAlpha[i]-'a'] = true;
		}

		for (int i = 0; i < 21; i++) {

			if(comb[i])
				nowAlpha[alpha[i]-'a'] = true;
			else {
				nowAlpha[alpha[i]-'a'] = false;
			}
		}
		
		int nowSum = 0;

		// N = 50
		// 50x7 = 350 
		for (string s : checkString) {

			// 해당 문자가 선택한 문자들로 가능한지 판단.
			bool isPossible = true;

			for (int i = 4; i < s.size() - 4; i++) {
				char c = s[i];
				if (!nowAlpha[c - 'a']) {
					isPossible = false;
					break;
				}
			}

			if (isPossible) {
				nowSum++;
			}

		}
		result = max(result, nowSum);

	} while (next_permutation(comb.begin(), comb.end()));

	cout << result << endl;

	return 0;
}