알고리즘 :: 백준 :: Bruteforce :: 1062:: 가르침

문제

문제접근

문제 이해

• 저번에 배웠던 교훈에 따라 효율성 신경쓰지말고 먼저 정답을 만들기에 집중했습니다.
  (AC는 받았지만 속도 느리다는 점 미리 밑밥 깔고 갑니다...ㅎㅎ)

• 문제를 요약하면, ''단어 N개 중 알파벳 K개로 표현할 수 있는 단어의 최대 개수를 구하세요'' 입니다.

• 문제 과정을 요약하면 다음과 같습니다.

  1. 26개 알파벳 중 K개를 중복없이 고릅니다. (조합)
  2. 단어 N개를 순회하며
  3. 해당 단어 속 단어들이 K개 알파벳에 포함되는지 검사합니다.

• '최대 개수'를 알기 위해서는 모든 조합을 검사해야 하므로 bruteforce 문제입니다.

  • 따라서 위 과정의 1번과 2번에서 경우의 수를 줄일 수 없습니다.
  • 하지만, 과연 그럴까요?

• Bruteforce이므로 탐색해야하는 범위 자체를 줄일 수는 없지만, 조금 효율적으로 조합을 구할 수 있는 방법이 있습니다.

• 바로, "남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다"라는 조건 덕분입니다.

• 단어를 최대한 읽기 위해서는 무조건 a, c, i, n, t 5글자를 알아야 합니다.

  • 따라서, 입력 K가 5보다 작다면 무조건 읽을 수 있는 단어 개수는 0입니다.
  • 따라서, 알파벳 a, c, i, n, t는 true로 놓고 출발합니다.
  • 따라서, 26개 중 K개 알파벳을 뽑는 문제는, 21개 중 K-5개 알파벳을 뽑는 문제로 바뀝니다.
  • 고려할 조합의 개수가 줄어듭니다.
    ($Max \ of \ _{26}C_K = \ _{26}C_{13} = 10,400,600 \ \ \rightarrow \ \ Max \ of \ _{21}C_{K-5} = _{21}C_{10} = 352,716$)

• 저는 alphabet[26] 과 perm[26] 이라는 bool 타입 배열 2개를 만들었습니다.

  • alphabet[26]: a, c, i, n, t 5글자를 항상 true로 가지고 있는 배열입니다.
  • perm[26]: 고른 K-5개의 알파벳을 false로 가지고 있는 배열입니다.
  • 21개 중 K-5개 알파벳을 고르는 과정을 코드로 구현하기 까다롭습니다.
    따라서, 만일 perm[]에 저장된 K-5개의 알파벳이 alphabet과 겹치는 경우는 continue;로 생략하도록 만들었습니다.

• 각 단어를 검사할 때 단어 길이가 짧기 때문에 for문을 이용해서 검사했습니다.
  하지만, 비트마스크를 이용하는 방법도 있습니다.

  • string 타입의 vector가 아니라 int형 vector를 만듭니다.
  • 단어를 입력받을 때, i번째 단어에 포함된 글자에 해당하는 비트를 set 해줍니다.
  • 검사할 때 해당 비트가 set인지 reset인지 검사하면 됩니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define NUMALPHA 26
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	int N, K, ans = 0;
	cin >> N >> K;
    
	vector<string> words(N);
	for (int i = 0; i < N; ++i) cin >> words[i];
	
	if (K < 5) { cout << ans; return 0; }
	
	vector<bool> alphabet(NUMALPHA, false);
	alphabet[0] = alphabet[2] = alphabet[8] = alphabet[13] = alphabet[19] = true;
	vector<bool> perm(NUMALPHA, true);
	for (int i = 0; i < K - 5; ++i) perm[i] = false;

	do {
			int cnt = 0;
			if (!perm[0] || !perm[2] || !perm[8] || !perm[13] || !perm[19]) continue;
			for (int i = 0; i < NUMALPHA; ++i)	// check readable alphabets.
				if (!perm[i]) alphabet[i] = true;
			for (const string& word : words) {	
				bool flag = true;
				for (size_t i = 0; i < word.length(); ++i)	// Is the word readable?
					if (!alphabet[word[i] - 'a']) { flag = false;  break; }
				if (flag) cnt++;
			}
			for (int i = 0; i < NUMALPHA; ++i)	// uncheck alphabets for next loop.
				if (!perm[i]) alphabet[i] = false;
			ans = max(ans, cnt);
	} while (next_permutation(begin(perm), end(perm))); 
	cout << ans;
}

결과