[BOJ 1062] 가르침

🔗Link

문제
풀이

💡Idea

26개의 알파벳 중 K개를 가르칠 수 있다. 단어에 A, C, I, N, T는 꼭 들어가기 때문에, 이 철자들은 꼭 배워야 한다. backtracking으로 배울 알파벳을 선택한 후 읽을 수 있는 단어가 몇 개인지 세어보면 되겠다. 단어의 최대 길이는 15이지만, 앞 뒤 4글자는 A, C, I, N, T이기 때문에, 가운데의 최대 7글자만 비교해주면 된다. 읽을 수 있는 최대 단어 개수가 총 단어의 개수와 같다면 더 탐색을 안 해도 된다.

시간복잡도
21개의 알파벳 중에서 K개를 고르는 $21Ck$번의 경우의 수가 생긴다. 최악의 경우 시간복잡도를 생각해보면, $21C10 = 352716$ 의 경우마다 50개의 단어의 7글자들을 비교해야 하니, $352716 \times 50 \times 7 = 123450600 \approx 10^8$ 정도로, 가지치기를 적당히 한다면 1초 내로 통과할 법하다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

int N, K;
string words[50];
bool canRead[26];
int maxCnt = 0;

void func(int k, int idx) {
	if (k == K-5) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			bool canReadWord = true;
			for (char c : words[i]) {
				if (canRead[c-'a']) continue;
				canReadWord = false;
				break;
			}
			if (canReadWord) cnt++;
		}
		maxCnt = max(maxCnt, cnt);
		if (maxCnt == N) {
			cout << maxCnt;
			exit(0);
		}
		return;
	}
	for(int i = idx; i < 26; i++){
		if (canRead[i]) continue;
		canRead[i] = true;
		func(k + 1, i);
		canRead[i] = false;
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	// 하나도 못 읽는 경우
	if (K < 5) {
		cout << 0;
		return 0;
	}

	for (int i = 0; i < N; i++) {
		cin >> words[i];
		words[i] = words[i].substr(4, words[i].size() - 8);
	}

	canRead['a' - 'a'] = true;
	canRead['c' - 'a'] = true;
	canRead['i' - 'a'] = true;
	canRead['n' - 'a'] = true;
	canRead['t' - 'a'] = true;

	func(0,1);

	cout << maxCnt;

	return 0;
}

🗨️ Side Notes

아자아자!