[백준/BOJ] 백준 9997번 : 폰트

www.acmicpc.net/problem/9997

9997번: 폰트

각 단어별로 가지고 있는 알파벳을 비트 연산으로 저장해 놓은 뒤, 저장한 값들은 모두 확인하여 해당 인덱스 단어를 포함할 때와 포함하지 않을 때를 고려해서 문제를 해결했다.

 

코드

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

int n;
vector<int> word_check;
int result = 0;

void Solve(int this_check, int index)
{
	if (index == n)
	{
		//a~z의 모든 알파벳이 체크되어 있을때
		if (this_check == ((1 << ('z' - 'a' + 1)) - 1))
			result++;

		return;
	}

	Solve(this_check | word_check[index], index + 1); //해당 인덱스 번째 단어를 포함할때
	Solve(this_check, index + 1); //해당 인덱스 번째 단어를 포함하지 않을때
}

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

	cin >> n;

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

		int this_check = 0;
		for (int j = 0; j < input.size(); j++)
		{
			this_check |= (1 << (input[j] - 'a')); //비트연산을 이용하여 어떤 알파벳을 가지고 있는지 체크한다
		}
		word_check.push_back(this_check);
	}

	Solve(0, 0);

	cout << result;

	return 0;
}