백준_1062_가르침

📍문제: https://www.acmicpc.net/problem/1062

1062번: 가르침

 

📍알고리즘: 브루트포스-비트마스크 (+브루트포스-재귀)

 

📍시간 복잡도:

1. 첫 접근법)

26개의 알파벳 중 K개를 고르는 경우의수(=2의 26승) * N개의 단어 * 각 단어에서 단어의 길이(문자 L개)만큼 배운 문자인지 검사

→ 2의 26승 * N * L (N 최대: 50, L 최대: 15) 👉 시간 초과

 

2. 문제의 조건(모든 단어에 anta, tica가 들어감) 고려해서 개선한 접근법)

a,n,t,i,c는 무조건 배워야 단어를 1개라도 읽을 수 있음 → (26-5)개의 알파벳 중 (K-5)개를 고르는 경우의수 

→ 2의 (26-5)승 * N * L (N 최대: 50, L 최대: 15) = 대략 200만 * 50 * 15 = 약 15억 👉 시간 초과

 

3. 비트마스크를 이용해서 개선한 접근법)

ⓐ 26개의 알파벳 중 K개를 고르는 경우의수(=2의 26승)

ⓑ N개의 단어

ⓒ 각 단어에서 단어의 길이(문자 L개)만큼 배운 문자인지 검사

이 세가지 중, ⓐ와 ⓑ는 줄일 수 없으므로 ⓒ를 비트마스크를 이용해서 줄인다. ⓐ는 재귀로 푼다.

→ 비트마스크의 시간복잡도는 O(1)이다. → 2의 (26-5)승 * N 👉 가능

 

📍아이디어:

① 단어를 저장할 때 i번째 알파벳이 단어에 포함되면, 오른쪽에서 i번째인 비트를 1로 저장.

Ex.) a,b,c,d가 알파벳의 전부일 때, 단어가 aadda 라면, 1001 저장.

 

② 배우는 문자도 마찬가지로 i번째 알파벳을 배우면 i번째 비트를 1로 저장.

 

→ ①을 W, ②를 L이라 하자. 단어에는 있는데 배운 문자에는 없으면 그 단어는 읽지 못한다. 즉, W의 특정 비트가 1인데 L의 특정 비트가 0이라면 그 단어는 읽지 못한다. 이 말은, W의 특정 비트가 1인데 ~L의 비트가 1이어서 둘을 AND 연산한 결과가 1이라면 그 단어를 읽지 못한다는 말이다. 그렇다면 연산 결과가 0이라면, 그 단어는 읽을 수 있다는 뜻이다.

 

📍~L (비트의 NOT 연산) 할 때 주의할 점:

int형 사용시 저장되는 값은 32비트 이므로 0000···1001을 반전시키면, 우리가 원하는 결과인 뒤의 1001만 반전되는것이  아니라, 앞도 1111···이 된다. 따라서, NOT 연산을 하는게 아니라, (1<<4) - 1 = 1111에서 1001을 빼는 연산을 하면 뒤의 1001만 반전된 결과를 얻을 수 있다.

 

📍코드:

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

int count(int learn, vector<int>& word) { // 읽을 수 있는 단어 개수 세기
	int cnt = 0;
	int size = word.size();
	for (int i = 0; i < size; i++) {
		if ((word[i] & ((1 << 26) - 1 - learn)) == 0) {
			cnt++;
		}
	}
	return cnt;
}

int solve(int index, int k, int learn, vector<int> &word) {
	// 실패한 경우
	if (k < 0) {
		return 0;
	}
	// 성공한 경우
	if (index == 26) {
		return count(learn, word);
	}
	// 다음 호출
	int ans = 0;
	// index번째 알파벳을 배움
	int tmp = solve(index + 1, k - 1, learn | (1 << index), word);
	if (ans < tmp) {
		ans = tmp;
	}
	// index번째 알파벳을 안배움
	if (index != 'a' - 'a' && index != 'n' - 'a' && index != 't' - 'a' && index != 'i' - 'a' && index != 'c' - 'a') { // a,n,t,i,c 는 무조건 배워야하므로
		tmp = solve(index + 1, k, learn, word);
		if (ans < tmp) {
			ans = tmp;
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, K;
	cin >> N >> K;
	vector<int> word(N); // 단어 자체를 저장하는 것이 아니라 단어에 포함된 알파벳을 비트로 저장
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (char x : s) {
			word[i] |= (1 << (x - 'a'));
		}
	}
	cout << solve(0, K, 0, word) << '\n';
	return 0;
}