[백준/BOJ] 백준 1062번 : 가르침

www.acmicpc.net/problem/1062

1062번: 가르침

각각 단어가 가지고 있는 알파벳의 정보를 비트 연산자로 저장해 놓는다. 그리고 a, c, i, n, t를 제외한 알파벳을 골라가는데, 알파벳을 고를 때도 고른 정보를 비트 연산자를 이용해 저장한다. 그리고 알파벳을 다 골랐을 때 고른 알파벳들로 단어를 만들 수 있는지 확인하는 것도 비트 연산을 통해 확인한다.

 

코드

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

int n, k;
vector<int> word_check;

int Solve(int select_check, int select_cnt, int before_select)
{
	int ret = 0;
	if (select_cnt == k) //알파벳을 다 골랐을때
	{
		//word_check[i]와 select_check(고른 알파벳 정보)를 & 연산을 통해 고른 알파벳들(select_check)로 해당 단어를 만들 수 있는지 확인한다
		for (int i = 0; i < word_check.size(); i++)
		{
			if ((word_check[i] & select_check) == word_check[i])
				ret++;
		}

		return ret;
	}

	for (int i = before_select + 1; i < 26; i++)
	{
		char this_alpha = 'a' + i;

		//a,c,i,n,t는 이미 골라져 있다
		if (this_alpha == 'a' || this_alpha == 'c' || this_alpha == 'i' || this_alpha == 'n' || this_alpha == 't')
			continue;

		select_check |= (1 << i); //i번째 알파벳 체크

		ret = max(ret, Solve(select_check, select_cnt + 1, i));

		select_check ^= (1 << i); //i번째 알파벳 체크 해제
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		//앞쪽의"anta", 뒤쪽의"tica"를 뺀 문자열을 구한다
		input = input.substr(4);
		input = input.substr(0, input.size() - 4);

		int check = 0;
		for (int j = 0; j < input.size(); j++) 
		{
			check |= (1 << (input[j] - 'a')); //해당 단어가 가지고 있는 문자를 비트연산을 이용해 구한다
		}

		word_check.push_back(check); 
	}

	//a,c,i,n,t는 무조건 있어한다
	int select_check = 0;
	select_check |= (1 << ('a' - 'a'));
	select_check |= (1 << ('c' - 'a'));
	select_check |= (1 << ('i' - 'a'));
	select_check |= (1 << ('n' - 'a'));
	select_check |= (1 << ('t' - 'a'));

	k = k - 5; //a,c,i,n,t를 고른것

	if (k < 0) //a,c,i,n,t도 고를 수 없을때
		cout << 0;

	else
		cout << Solve(select_check, 0, -1);

	return 0;
}