[백준1062] 가르침 (C++)

📌 문제

BOJ 바로가기

읽을 수 있는 단어의 개수가 최대가 되게끔 k개의 알파벳을 골라서 배워야 한다. 가능한 모든 조합을 탐색해야 한다.

🗡 풀이

✨ 비트마스크를 이용해 모든 조합을 체크할 수 있다.

📍 a, c, i, n, t 이 다섯 글자는 꼭 배워야 한다. 이 글자 없이는 한 단어도 읽을 수 있다. 따라서 다음과 같이 집합 s에 다섯 글자를 추가해 준다.

 	s = (s | (1 << ('a' - 'a')));
	s = (s | (1 << ('c' - 'a')));
	s = (s | (1 << ('i' - 'a')));
	s = (s | (1 << ('n' - 'a')));
	s = (s | (1 << ('t' - 'a')));

📍 다섯 글자만 배운 경우의 부분집합부터 시작해 모든 부분집합을 탐색한다.
for(bit = s; bit < (1 << 26); bit++)

📍 bit는 s를 꼭 포함하고 있어야 하므로 다음 소스코드를 for문의 가장 앞부분에 추가한다.
if ((bit & s) != s) continue;

이 코드를 뒤에 넣으면 시간초과가 뜬다. 조건에 맞지 않는 경우는 최대한 빨리 걸러줘야 한다.

📍 각 단어를 배울 수 있는지 체크한다. 이 때, 단어의 4번째 인덱스부터 (length - 4 - 1)번째 인덱스까지만 체크한다.

📍 maxi에 배울 수 있는 단어의 개수의 최댓값을 갱신해 넣는다.

🚩 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, k, s = 0, maxi = 0;
	string word[50];
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> word[i];
	if (k < 5) {
		cout << '0';
		return 0;
	}
	// s에 필수 문자 5개 추가
	s = (s | (1 << ('a' - 'a')));
	s = (s | (1 << ('c' - 'a')));
	s = (s | (1 << ('i' - 'a')));
	s = (s | (1 << ('n' - 'a')));
	s = (s | (1 << ('t' - 'a')));
	// 모든 부분집합 탐색
	for (int bit = s; bit < (1 << 26); bit++) {
		if ((bit & s) != s) continue; // bit가 s를 포함하고 있지 않다면 바로 continue
		int cnt = 0;
		// 원소 개수 검사
		for (int i = 0; i < 26; i++) {
			if (bit & (1 << i))
				cnt++;
		}
		// 필수 문자 5개를 포함해 k개를 골랐을 경우
		if (cnt == k) {
			int wc = 0;
			for (int i = 0; i < n; i++) {
				bool flag = true;
				for (int j = 4; j < word[i].length() - 4; j++) { // anta ~ tica의 ~ 부분만 탐색
					if (!(bit & (1 << (word[i][j] - 'a')))) {
						flag = false;
						break;
					}
				}
				if (flag)
					wc++;
			}
			maxi = max(maxi, wc);
		}
	}
	cout << maxi;
}