백준[1062]가르침

아이디어

• [비트마스킹] 을 사용할 줄 안다.
• [재귀함수] 를 통해 조합을 뽑을 줄 안다.

접근방식

1. 비트마스킹을 통해 각 단어를 비트로 바꿔 벡터에 저장한다
2. 재귀함수를 통해 조합하여 만들 수 있는 알파벳의 집합을 전부 구해, 비트마스킹으로 바꾸어 벡터에 저장한다
3. 알파벳의 집합과 각 단어를 비교하여 최대값을 구한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
#include <stack>

using namespace std;

int answer = 0;
int end_bit = 26;

vector<int> check_mask; //check 하기위해 만들어진 char의 집합들
vector<int> bit_words; //단어들을 bit로 만들어 보관한것

void check(int bits_for_check, int now_pos, int cnt)
{
	if (cnt == 0)
	{
		check_mask.push_back(bits_for_check);
		return;
	}

	if (now_pos == end_bit)
		return;

	
	int new_bits_for_check = (bits_for_check | (1 << now_pos));

	check(new_bits_for_check, now_pos + 1, cnt - 1);
	check(bits_for_check, now_pos + 1, cnt);
	
}

int main()
{
	// 'a' == 97, 'z' == 122
	// bitmasks == 0 ~ 25
	
	int word, spell; scanf("%d %d", &word, &spell);

	vector<string> words;
	
	for (int i = 0; i < word; i++)
	{
		string s; cin >> s;
		words.push_back(s);
	}

	if (spell < 5)
	{
		printf("0");
		return 0;
	}

	for (string s : words)
	{
		int new_bit = 0;
		//bitmask에 각 char별로 마킹하기
		for (char c : s)
		{
			new_bit |= (1 << (c - 97));
		}
		bit_words.push_back(new_bit);

	}

	check(0, 0, spell);

	int answer = 0;

	for (int check_bit : check_mask)
	{
		int new_answer = 0;
		for (int bit_word : bit_words)
		{
			if ((check_bit & bit_word) == bit_word) new_answer++;
		}

		if (new_answer > answer) answer = new_answer;
	}

	printf("%d\n", answer);

	return 0;
}

평가

비트마스킹을 안다면 쉽게 풀 수 있는 문제입니다. 저는 비트마스킹도 몰랐고, 조합을 뽑으려면 재귀함수를 사용하면 된다는 아이디어가 떠오르지 않아 애를 많이 먹었던 문제입니다.

비트마스킹에 관해선 https://rebro.kr/63 이분의 설명을 참조하였습니다.

또한 비트마스킹을 사용하지 않고, dfs를 사용한 백트레킹을 통해서도 문제를 해결할 수 있습니다. 하지만 그렇게 하기 위해선 a,n,t,i,c 에 관하여 미리 체크를 해주지 않으면 시간초과가 날 수 있는 가능성이 존재하기에 주의해야 합니다.

* 배울 것 :
1) 조합을 뽑는 문제는 [재귀함수]에서 영감을 얻자
2) input이 작으면 [비트마스킹]을 생각하자